[gambit-list] Computing a billion decimal digits of pi

Bakul Shah bakul at bitblocks.com
Thu Jun 13 01:25:15 EDT 2013


On Wed, 12 Jun 2013 22:05:20 CDT Phil Bewig <pbewig at gmail.com> wrote:
> 
> What is the time complexity of the Chudnovsky algorithm?

I don't really know. On a quick search I didn't find anything
but I suspect it is dominated by the multiplication cost. The
Schnhage-Strassen multiplication algorithm (using FFT) has a
complexity of O(N log N log log N),where N is the length of
the number. To get an idea we can compute the ratio of time
cost for 10N and N. For N = 1000000 it is 12.9 and N = 10^7
it is about 12.  Empirically it is 15.8 in Brad's tests and
16.3 for gmp-chudnovksy.c (10 seconds for 10^7, 163 seconds
for 10^8). Between 10^8 & 10^9 Brad had to use Karatsuba and
the ratio went up to about 32.

It probably wouldn't be hard to figure out the number of
additions, multiplications etc. as a function of how many
terms are being evaluated. Each term adds a little over 14
digits.  From that you can derive the compexity figure.
Another interesting fact will be the memory traffic as a
function of N! This can also be useful in gauging the
effectiveness of any parallelizing.



More information about the Gambit-list mailing list