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

Phil Bewig pbewig at gmail.com
Wed Jun 12 23:05:20 EDT 2013


What is the time complexity of the Chudnovsky algorithm?


On Wed, Jun 12, 2013 at 6:06 PM, Bakul Shah <bakul at bitblocks.com> wrote:

> On Wed, 12 Jun 2013 13:07:45 EDT Bradley Lucier <lucier at 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 at iro.umontreal.ca
> https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20130612/25ce477f/attachment.htm>


More information about the Gambit-list mailing list