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

Marc Feeley feeley at iro.umontreal.ca
Wed Jun 12 13:20:19 EDT 2013


That is really… I mean *really* cool!  One billion digits of pi in less than 12 hours.  Amazing!

This is a testament to your hard work on implementing Gambit's bignum routines.

Are we close to setting a record?  I'm hoping we can parallelize soon!

Marc

P.S. it is nice to know that the last 5 digits of the 1,000,000,000 digits you have computed are correct.  Too bad we know nothing about the other 999,999,995 digits.  ;-)

On Jun 12, 2013, at 10:07 AM, Bradley Lucier <lucier at math.purdue.edu> wrote:

> Just for laughs and giggles, I decided to calculate 1,000,000,000 (yes, 
> 9 zeros) digits of pi using Bakul Shah's Scheme program implementing the 
> Chudnovsky algorithm.  The computation used one CPU core:
> 
> model name    : Intel(R) Xeon(R) CPU           X5570  @ 2.93GHz
> 
> with a pretty good memory subsystem with 72GB of memory using this 
> version of Gambit:
> 
> leibniz-173% gsi -v
> v4.6.9 20130611050302 x86_64-unknown-linux-gnu "./configure 
> 'CC=/pkgs/gcc-4.7.2/bin/gcc -march=native -fschedule-insns 
> -frename-registers' '--enable-single-host' '--enable-multiple-versions' 
> '--enable-shared' '--prefix=/pkgs/Gambit-C'"
> 
> The timings are after the signature.
> 
> 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.
> 
> So while the CPU time goes up roughly by a factor of 16 when the number 
> of digits of pi is multiplied by 10 for computations involving "small" 
> bignums (with no more than a billion bits), the computation of a billion 
> digits of pi takes about 32 times as long as the computation of 100 
> million digits (using "large" bignums).
> 
> As Bakul points out, the algorithm is easily parallelized, but I didn't 
> want to do that yet.  (This is an older machine with 8 cores and 16 
> virtual CPUs.)
> 
> Brad
> 
> 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!
> 
> PPS:  The last five digits are correct, according to this web page:
> 
> http://gc3.net84.net/pi.htm
> 
> Whew!
> 
> leibniz-172% gsi chud2
> Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 
> 10, CPU time: 0..
> Last 5 digits 26535.
> Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 
> 100, CPU time: 0..
> Last 5 digits 70679.
> Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 
> 1000, CPU time: 0..
> Last 5 digits 1989.
> Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 
> 10000, CPU time: .020000000000000004.
> Last 5 digits 75678.
> Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 
> 100000, CPU time: .340022.
> Last 5 digits 24646.
> 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 
> 10000000, CPU time: 83.765235.
> Last 5 digits 55897.
> Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 
> 100000000, CPU time: 1327.790981.
> Last 5 digits 51592.
> Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 
> 1000000000, CPU time: 41907.731069.
> Last 5 digits 45519.
> 
> 
> _______________________________________________
> Gambit-list mailing list
> Gambit-list at iro.umontreal.ca
> https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list




More information about the Gambit-list mailing list