// Purpose: computes the first n decimal digits of Pi
// uses a variant of the spigot algorithm valid for n < 54900
// Author: Peter Luschny
// Date: 2000-05-16/18:45 (Rev. 0)
// This file was released to the public domain.
// Feel free to use this source code in any way.
// Want no money, no credit, no admiration.

// CREDITS
// based on ideas of A. Sale (1968)
// algorithm due to D. Saada (1988) and S. Rabinowitz (1991)
// proof (with some bugs) due to S. Rabinowitz and S. Wagon (1995)
// C-implementation due to J. Arndt, C. Haenel, D. Winter, A. Flammenkamp
// this Java-implementation adopts and modifies this C-implementation, 
// see page 84 in: J. Arndt, C. Haenel: "Pi - Algorithmen, Computer, Arithmetik"
// 2. edition, Springer 2000. Also highly recommended:
// Jean-Paul Delahaye: "Pi - die Story", Birkhauser 1999


package de.luschny.math.numbers;

import java.util.Arrays;

/*
 * Computes the first n decimal digits of Pi,
 * uses a variant of the spigot algorithm 
 * valid for n < 54900.
 */

public class PiSpigot
{
    public static StringBuffer(int digits)
    {
        if ( digits > 54900)
        {
            throw new IllegalArgumentException("n must be <= 54900");
        }

        final StringBuffer pi = new StringBuffer(digits);
        final String[] zero = { "0", "00", "000" };
        int d = 0, e, b, g, r;
        int c = (digits / 4 + 1) * 14;
        final int[] a = new int[c];
        final int f = 10000;

        Arrays.fill(a, 20000000);

        while ((b = c -= 14) > 0)
        {
             d = e = d % f;

             while (--b > 0)
             {
                  d = d * b + a[b];
                  g = (b << 1) - 1;
                  a[b] = (d % g) * f;
                  d /= g;
             }

             r = e + d / f;

             if (r < 1000)
             {
                  pi.append(zero[r > 99 ? 0 : r > 9 ? 1 : 2]);
             }
             pi.append(r);
        }
        return pi;
    }

    public static void main(String[] ignore)
    {
         long start = System.currentTimeMillis();
         StringBuffer b = pi(15000);
         long stop = System.currentTimeMillis();
         double sec = (double) (stop - start) / 1000.;
         System.out.println(b);
         System.out.println("Computing time in seconds: " + sec);
    }
}