[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