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@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:
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@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list