来自spigot算法的错误答案

Question

我正在编写spigot算法，用于在ada中显示pi的数字，但我的输出是错误的，并且我找不出原因

我尝试过调整循环的范围和输出数据的不同方式，但都不能正常工作

with ada.integer_text_io; use ada.integer_text_io;
with Ada.Text_IO; use Ada.Text_IO;

procedure Spigot is
    n : constant Integer := 1000;
    length : constant Integer := 10*n/3+1;
    x,q,nines,predigit :Integer :=0;
    a: array (0..length) of Integer;

begin
    nines:=0;
    predigit:=0;

    for j in 0..length loop
        a(j):=2;
    end loop;

    for j in  1..n loop
        q:=0;
        for i in reverse 1..length loop
            x:=10*a(i) + q*i;
            a(i):= x mod (2*i-1);
            q:= x/(2*i-1);
        end loop;

        a(1):= q mod 10;
        q:=q/10;

        if q = 9 then
            nines:=nines+1;
        elsif q = 10 then
            put(predigit+1);
            for k in 0..nines loop
                put("0");
            end loop;
            predigit:=0;
            nines:=0;
        else
            put(predigit);
            predigit:=q;
            if nines/=0 then
                for k in 0..nines loop
                    put("9");
                end loop;
                nines:=0;
            end if;      
        end if;   
    end loop;
    put(predigit);
end Spigot;

所以它应该只显示在0 3 1 4 1 5 9 2 6 5 3 5 8 9...但我得到的输出是0 3 1 4 1 599 2 6 5 3 5 89...它一次应该只有1位数，而且pi的输出值也不完全正确

Answer 1

我认为你在翻译this answer。

您需要更加小心您的索引和循环范围；例如，您已经将

for(int i = len; i > 0; --i) {
  int x  = 10 * A[i-1] + q*i;
  A[i-1] = x % (2*i - 1);
  q = x / (2*i - 1);
}

作为

for i in reverse 1..length loop
    x:=10*a(i) + q*i;
    a(i):= x mod (2*i-1);
    q:= x/(2*i-1);
end loop;

循环范围是相同的。但是在a(i)行中，C代码使用A[i-1]，而您的代码使用seocnd；与第三行类似。

稍后，对于

  for (int k = 0; k < nines; ++k) {
    printf("%d", 0);
  }

你有

  for k in 0..nines loop
      put("0");
  end loop;

其中C循环从0运行到nines - 1，但是您的循环从0运行到nines。因此，您比应该多放了一个0 (稍后，对9也是如此)。

此外，您还应该使用put (predigit, width=> 0)。

Answer 2

我对算法的了解还不够深入，无法讨论数字为什么会出错，但我确实注意到了一些问题：

1. 您的数组定义为边界0 ..长度，这会给你一个额外的元素，在你的循环中进行计算，你从1..length循环，这是可以的，但是你没有一致地调整变量i。数组索引需要比实际计算中使用的i小1(请记住，它们仍然必须正确地位于数组的边界内)。例如

x:=10*a(i) + q*i；

需要要么是

x:=10*a(i-1) + q*i；

或

x:=10*a(i) + q*(i+1)；

这取决于您决定的数组边界。这适用于代码中的多行。当你的数组从0开始，你的循环输出"0“和"9”应该是1..length或0时，请看这个Stackoverflow thread

• You A(1)。length-1

• 使用Integer_Text_IO.Put打印数字时，需要将宽度指定为1以消除空格

可能还有更多，这就是我看到的。