[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