[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