Compute pi in hexadecimal, an implement for BBP formula

Question

I was trying to make this implement works, but fail to find the bug that make my test unit fail. Could you tell me where the bug might be? I am quite sure that the algorithm is right.

package piwords;

public class PiGenerator {
    /**
     * Returns precision hexadecimal digits of the fractional part of pi.
     * Returns digits in most significant to least significant order.
     * 
     * If precision < 0, return null.
     * 
     * @param precision The number of digits after the decimal place to
     *                  retrieve.
     * @return precision digits of pi in hexadecimal.
     */
    public static int[] computePiInHex(int precision) {
        // TODO: Implement (Problem 1.d)
        int [] b = new int [precision];
        for (int a = 0; a < precision; a++) {
            b[a] = piDigit( a + 1 );
        }
        return b;
    }

    /**
     * Computes a^b mod m
     * 
     * If a < 0, b < 0, or m < 0, return -1.
     * 
     * @param a
     * @param b
     * @param m
     * @return a^b mod m
     */
    public static int powerMod(int a, int b, int m) {
        // TODO: Implement (Problem 1.b)
        if (( a > 0 ) && ( b > 0 ) && ( m > 0 )) {
            Double t = new Double(0);
            t = Math.pow(a, b);
            Double re = new Double( t % m );
            return re.intValue();
        }
        return -1;
    }

    /**
     * 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;   // little bug, should be as following
        return ( ( s + t ) - Math.floor( s + t ) );
    }
}

===================================================================

this is my test class

==================================================================

package piwords;

import static org.junit.Assert.*;

import org.junit.Test;
import org.junit.experimental.theories.suppliers.TestedOn;

public class PiGeneratorTest {
    @Test
    public void basicPowerModTest() {
        // 5^7 mod 23 = 17
        assertEquals(17, PiGenerator.powerMod(5, 7, 23));
        assertEquals(44, PiGenerator.powerMod(11, 5, 51));
    }

    // TODO: Write more tests (Problem 1.a, 1.c)
    @Test
    public void testComputePiInHex() {
        int[] a = {2, 4, 3, 15, 6};
        assertArrayEquals(a, PiGenerator.computePiInHex(5));
    }
}

Answer 1

You should change b > 0 to b >= 0, then the result seems to be ok.
Note that for larger values you can't rely on double numbers (with pow) in powerMod, as they have limited precision. You should work with integers and use this equality:

a^(b+c) mod m = (a^b mod m) * (a^c mod m) mod m