What is the time complexity of the Chudnovsky algorithm?
On Wed, Jun 12, 2013 at 6:06 PM, Bakul Shah bakul@bitblocks.com wrote:
On Wed, 12 Jun 2013 13:07:45 EDT Bradley Lucier lucier@math.purdue.edu wrote:
Going from 100 million to a billion digits shows the limitation of Gambit's current FFT implementation of bignum multiplication. Gambit's FFT algorithm is correct only when the product of two bignums has no more than a billion bits; when the product will have more than a billion bits, then Karatsuba decomposition is used until the intermediate results have no more than a billion bits.
This will help when you parallelize using GPUs! FFT multiplies on GPUs will not be able to handle very long numbers.
PS: I'm sorry I didn't try this computation two years ago:
http://www.pcmag.com/article2/0,2817,2383975,00.asp
Ha!!! And this isn't the Onion!
Onion material but folks @ pcmag don't know it! They seem to have gotten the wrong end of the stick. I followed the chain and I think they are talking about what is reported here: http://carma.newcastle.edu.au/jon/bbp-bluegene.pdf or may be an earlier article on the same. This paper is much more interesting!
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000, CPU time: 5.140321. Last 5 digits 58151.
...
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000000, CPU time: 41907.731069. Last 5 digits 45519.
Quite impressive!
For comparison, gmp-chudnovksy.c does a million digits in 0.61s on 3.6Ghz 8core AMD FX, and 11 seconds on a 700Mhz RaspberryPi! For a billion digits it takes 2493 seconds.
chud2 / gmp-chudnovsky ratio of about of 8 (@ 10^6 digits) and 16 (@ 10^9 digits) is most due to the fact that for big nums gmp has processor specific optimized assmebly code. And gambit uses double the space due to portable C code. Right there you lose a factor of two!
The current record is 10 trillion (10^13) digits of pi. You'd need more than a single 2TB disk to store one such 10^13 digit number! Any arithmetic operation on such large numbers is essentially an exercise in streaming disks. And to do so efficiently you'd need some IO parallelism!
To allow such things you'd need some sort of pluggable bignum architecture. _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list