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

Bradley Lucier lucier at math.purdue.edu
Wed Jun 12 13:07:45 EDT 2013


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.





More information about the Gambit-list mailing list