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@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