[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