[gambit-list] Computing pi with parallel gambit

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


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 

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.


More information about the Gambit-list mailing list