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