How did the following piece of Java code calculate the digits of Pi?

Question

Which algorithm/formula does the below code use?

    /**
 * Computes the nth digit of Pi in base-16.
 * 
 * If n < 0, return -1.
 * 
 * @param n The digit of Pi to retrieve in base-16.
 * @return The nth digit of Pi in base-16.
 */
public static int piDigit(int n) {
    if (n < 0) return -1;

    n -= 1;
    double x = 4 * piTerm(1, n) - 2 * piTerm(4, n) -
               piTerm(5, n) - piTerm(6, n);
    x = x - Math.floor(x);

    return (int)(x * 16);
}

private static double piTerm(int j, int n) {
    // Calculate the left sum
    double s = 0;
    for (int k = 0; k <= n; ++k) {
        int r = 8 * k + j;
        s += powerMod(16, n-k, r) / (double) r;
        s = s - Math.floor(s);
    }

    // Calculate the right sum
    double t = 0;
    int k = n+1;
    // Keep iterating until t converges (stops changing)
    while (true) {
        int r = 8 * k + j;
        double newt = t + Math.pow(16, n-k) / r;
        if (t == newt) {
            break;
        } else {
            t = newt;
        }
        ++k;
    }

    return s+t;
}

This code was already written for us in our problem set. I can't find which algorithm/formula it uses and I'm curious about it. I suspect that this is a simple algorithm, but I can't find the formula online based on this piece of code only.

Ok. I will not get in depth with your algorithm but in this topic it is shown how to calculate pi iterativly http://stackoverflow.com/questions/39395/how-do-i-calculate-pi-in-c. In your case there is propably some yet other iterative algorithm. — gregory561, Sep 16 '12 at 18:29
This is a bit random, but do you have the code for `powerMod()` function that's used inside `piTerm()`? — Mark Biek, May 22 '13 at 19:25

score 10 · Accepted Answer · edited Dec 02 '13 at 17:31

10

As far as I can see, it is the Bailey-Borwein-Plouffe-Algorithm to calculate a n-th digit of pi without knowing the (n-1)th digit. The representation of pi is on base-16 here.

Formula to calculate the Nth digit of pi

See the Homepage of Bailey: http://crd-legacy.lbl.gov/~dhbailey/

edited Dec 02 '13 at 17:31

DwB

37,124
11
56
82

answered Sep 16 '12 at 18:27

Andreas

1,334
1
10
21

How did the following piece of Java code calculate the digits of Pi?

1 Answers1