Implementing the Spigot algorithm for π (pi)

Question

I'm having a hard time understanding the Spigot algorithm for π (pi) found here at the bottom of the page.

I'm getting lost at the bottom of part 2 "Put A into regular form", I'm not exactly sure how to implement this in C (or any language really)

Answer 1

  #include <math.h>
  #include <stdio.h>
  #define N 100

  int len = floor(10 * N/3) + 1;
  int A[len];

  for(int i = 0; i < len; ++i) {
    A[i] = 2;
  }

  int nines    = 0;
  int predigit = 0;

  for(int j = 1; j < N + 1; ++j) {        
    int q = 0;

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

    A[0] = q%10;
    q    = q/10;

    if (9 == q) {
      ++nines;
    }
    else if (10 == q) {
      printf("%d", predigit + 1);

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

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

        nines = 0;
      }
    }
  }
  printf("%d", predigit);

Answer 2

I am seeing a difference in the o/p digits of the above spigot pi program when compared with http://www.numberworld.org/misc_runs/pi-10t/details.html

Correct Value of 50 digits of Pi : http://www.numberworld.org/misc_runs/pi-10t/details.html

3.

1415926535 8979323846 2643383279 5028841971 6939937510

Above spigot pi :

3.

1415926535 8979323846 2643383279 5**(0)**28841971 6939937510

                                     ^^^ zero missing

Changed the 4 digits per loop to 8 digits by modifying long f = 100000000;

produced the correct result.

Answer 3

// Spigot program for pi to NDIGITS decimals.
// 4 digits per loop.
// Thanks to Dik T. Winter and Achim Flammenkamp who originally made a compressed version of this. 
 
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
 
#define NDIGITS 15536          //max digits to compute
#define LEN (NDIGITS/4+1)*14   //nec. array length
 
long a[LEN];                   //array of 4-digit-decimals
long b;                        //nominator prev. base
long c = LEN;                  //index
long d;                        //accumulator and carry
long e = 0;                    //save previous 4 digits
long f = 10000;                //new base, 4 decimal digits
long g;                        //denom previous base
long h = 0;                    //init switch
 
int main(void) {
        for(; (b=c-=14) > 0 ;){    //outer loop: 4 digits per loop
                for(; --b > 0 ;){      //inner loop: radix conv
                        d *= b;            //acc *= nom prev base
                        if( h == 0 )
                                d += 2000*f;   //first outer loop
                        else
                                d += a[b]*f;   //non-first outer loop
                        g=b+b-1;           //denom prev base
                        a[b] = d % g;
                        d /= g;            //save carry
                }
                h = printf("%.4d",e+d/f);//print prev 4 digits
                                         // %.4d to add leading zeros
                d = e = d % f;         //save currently 4 digits
                                       //assure a small enough d
        }
        getchar();
        return 0;
}