[gambit-list] Computing pi with parallel gambit

Bradley Lucier lucier at math.purdue.edu
Sun Nov 27 15:08:49 EST 2016


Marc:

Because of accumulated roundoff error in IEEE floating-point arithmetic, 
Gambit's FFT-based bignum multiplication algorithm is limited to 
multiplying two numbers each of which has <= 2^{29} bits (on a 64-bit 
machine).

Multiplying larger numbers falls back on Karatsuba multiplication, which 
cuts the size of the multiplicands roughly in half in each step, until 
you get back down to numbers of <= 2^{29} bits again, in which case FFT 
is used again.

So, in fact, to compute a billion decimal digits of pi, we rely on 
Karatsuba to do the largest multiplications (and divisions and square 
roots, since they all reduce to multiplication).

On a machine with enough memory, all the "sub-multiplications" in 
Karatsuba can be done in parallel.  I haven't figured out how much 
memory is needed; it takes a few GB of temporary RAM to multiply the 
largest numbers with the FFT algorithm.

I believe it took about 16GB total to calculate a billion decimal digits 
of pi using the current serial algorithm.

Once parallel gambit is usable, computing pi to a billion (or even 10 
billion, who knows) digits by parallelizing the larger Karatsuba 
multiplications might be a good test of the system.

Brad



More information about the Gambit-list mailing list