Wrong answer from spigot algorithm

Question

I'm coding the spigot algorithm for displaying digits of pi in ada, but my output is wrong and I can't figure out why

I've tried messing with the range of my loops and different ways to output my data but nothings worked properly

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;

so it should just be displayed at 0 3 1 4 1 5 9 2 6 5 3 5 8 9... but the output i get is 0 3 1 4 1 599 2 6 5 3 5 89... it should only be 1 digit at a time and also the outputted values for pi aren't completely correct

Answer 1

I think you are translating this answer.

You need to be more careful of your indices and your loop ranges; for example, you’ve translated

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);
}

as

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;

The loop ranges are the same. But in the seocnd line, the C code uses A[i-1], whereas yours uses a(i); similarly in the third line.

Later, for

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

you have

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

in which the C loop runs from 0 to nines - 1, but yours runs from 0 to nines. So you put out one more 0 than you should (and later on, likewise for 9s).

Also, you should use put (predigit, width=> 0).

Answer 2

I don't know the algorithm well enough to talk about why the digits are off, but I did notice some issues:

1. Your array is defined with bounds 0 .. Length, which would give you 1 extra element

2. In your loop that does the calculation, you loop from 1..length, which is ok, but you don't adjust the variable i consistently. The array indices need to be one less than the i's used in the actual calculations (keep in mind they still have to be correctly in bounds of your array). For example

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

   needs to either be

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

   or

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

   depending on what you decide your array bounds to be. This applies to multiple lines in your code. See this Stackoverflow thread

3. You assign A(1) when your array starts at 0

4. Your loops to print out "0" and "9" should be either 1..length or 0 .. length-1
5. When you print the digits using Integer_Text_IO.Put, you need to specify a width of 1 to get rid of the spaces

There might be more, that's all I saw.