On Wed, 12 Jun 2013 22:05:20 CDT Phil Bewig pbewig@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.