CODEWITHSUNDEEP
javaalgorithmmathpidigit
user2268648
user2268648

Reputation: 21

Making BBP algorithm for Java, computing nth digit

I have started a java project for computing the n-th digit of pi, and decided to use the BBP algorithm. In my output (in another class) I have been getting some weird math errors, and I don't know where it is from. So, I don't think I am putting the algorithm in the code correctly.

I got the algorithm from http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula

Here's my code:

import java.lang.Math;
import java.lang.Math.*;
public class Pi
{
public static double getDigit(int n, int infinity)
{   int pow = 0;
    double[] sums = new double[4];
    int tot = 0;
    int result = 0;
    double fraction = 0;
    for(int x = 0; x < 4; x++)
    {
        for(int k = 0; k < n; k++)
        {
            tot = 8 * k + 1;
            if(x == 1)
                tot += 3;
            else if(x > 1)
                tot++;
            pow = n-k;
            result = modular_pow(16, pow, tot);
            sums[x] += (double)result / (double)tot;
        }
        for(int i = n + 1; i < infinity; i++)
        {
            tot = 8 * i + 1;
            if(x == 1)
                tot += 3;
            else if(x > 1)
                tot++;
            fraction = Math.pow(16.0, (double)pow);
            sums[x] += fraction / (double)tot;
        }
    }
    return 4 * sums[0] - 2 * sums[1] - sums[2] - sums[3];
}
public static int modular_pow(int base, int exponent, int modulus)
    {
    int result = 1;
    while(exponent > 0)
    {
        if (exponent % 2 == 1)
            result = (result * base) % modulus;
        exponent--;
        base = (base * base) % modulus;
    }
    return result;
}

Thanks in advance.

Upvotes: 2

Views: 1496

Answers (1)

James Gallicchio
James Gallicchio

Reputation: 11

Firstly, apologies for necro-ing an old post, but there is a severe lack of explanation of the BBP algorithm being applied meaningfully and so I think this might still be useful to some people who want to look into it.

Based on the Wikipedia article, the result you're returning needs to be stripped of its integer part (leaving the fractional part) and then multiplied by 16. This should leave the integer part as a representation of the nth hex digit of pi. I'll test it out tomorrow and see if that helps. Otherwise, great implementation, easy to understand and efficiently done.

Upvotes: 1

Related Questions