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