[gambit-list] Computing pi with parallel gambit

Marc Feeley feeley at iro.umontreal.ca
Mon Nov 28 10:56:34 EST 2016


Yes parallelizing Karatsuba multiplication should be very easy.  That will make an interesting experiment when the multiple threaded VM configuration is stable.  I expect very close to linear speedup given the independent sub-multiplications.

Marc

> On Nov 27, 2016, at 3:08 PM, Bradley Lucier <lucier at math.purdue.edu> wrote:
> 
> 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