Gambit versus Python+GMP: Timing for Chudnovskys' algorithm for pi
Bakul Shah wrote a particularly elegant Scheme program for Chudnovskys' algorithm for pi based on the Common Lisp program here: https://bitbucket.org/tarballs_are_good/numericl/src/5fe8fe7089f48ab1c8a3886... Nick Craig-Wood wrote a Python program using the GMP multiprecision library that appears to use exactly the same algorithm here: http://www.craig-wood.com/nick/articles/pi-chudnovsky/ I modified both programs a bit and include them here. They time the calculation of $10^n$ digits of pi for $n=1,2,3,4,5,6,7$. The results are heine:~/programs/gambiteer/gambit> !py python pi_chudnovsky_bs_gmpy.py 31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679 ('chudnovsky_gmpy_mpz_bs: digits', 10, 'time', 1.0967254638671875e-05) ('chudnovsky_gmpy_mpz_bs: digits', 100, 'time', 3.0040740966796875e-05) Last 5 digits 70679 OK ('chudnovsky_gmpy_mpz_bs: digits', 1000, 'time', 0.00025582313537597656) Last 5 digits 01989 OK ('chudnovsky_gmpy_mpz_bs: digits', 10000, 'time', 0.00386810302734375) Last 5 digits 75678 OK ('chudnovsky_gmpy_mpz_bs: digits', 100000, 'time', 0.0834801197052002) Last 5 digits 24646 OK ('chudnovsky_gmpy_mpz_bs: digits', 1000000, 'time', 1.655979871749878) Last 5 digits 58151 OK ('chudnovsky_gmpy_mpz_bs: digits', 10000000, 'time', 30.67442488670349) Last 5 digits 55897 OK heine:~/programs/gambiteer/gambit> gsi chud1.scm 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: .004. Last 5 digits 1989. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000, CPU time: .028. Last 5 digits 75678. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000, CPU time: .472. Last 5 digits 24646. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000, CPU time: 6.448. Last 5 digits 58151. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000000, CPU time: 98.612. Last 5 digits 55897. So it appears that for this algorithm applied to large integers, GMP's bignum routines are about 3-4 times as fast as Gambit's bignum routines. Not so bad. For smaller bignums, GMP has a bigger advantage. The C program gmp-chudnovsky.c includes certain optimizations to this basic algorithm: http://gmplib.org/pi-with-gmp.html ftp://ftp.gmplib.org/pub/misc/gmp-chudnovsky.c On my machine, compiled with gcc -O3 -march=native -o gmp-chudnovsky gmp-chudnovsky.c -lgmp -lm the CPU times for 1,000,000 and 10,000,000 digits are 1.064 and 18.200 seconds, respectively. This is with a somewhat older machine model name : Intel(R) Core(TM)2 Quad CPU Q8200 @ 2.33GHz running Ubuntu 13.04 with heine:~/programs/gambiteer/gambit> gcc -v Using built-in specs. COLLECT_GCC=gcc COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.7/lto-wrapper Target: x86_64-linux-gnu Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.7.3-1ubuntu1' --with-bugurl=file:///usr/share/doc/gcc-4.7/README.Bugs --enable-languages=c,c++,go,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.7 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.7 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --with-system-zlib --enable-objc-gc --with-cloog --enable-cloog-backend=ppl --disable-cloog-version-check --disable-ppl-version-check --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu Thread model: posix gcc version 4.7.3 (Ubuntu/Linaro 4.7.3-1ubuntu1) heine:~/programs/gambiteer/gambit> gsi -v v4.6.9 20130607151908 x86_64-unknown-linux-gnu "./configure '--enable-single-host' '--enable-multiple-versions' '--enable-shared'" and the Ubuntu-provided GMP 5.0.5. (I'm sure the GMP folks have a better way to build GMP on my machine than the "generic" 64-bit version provided by Ubuntu.) Brad
Hi Bradley, Interesting. Nice numbers! Was your Gambit pi-calculator compiled with (declare (not safe)) and any other related setting for optimizing speed, like increasing inlining, setting mostly generic and inlining standard and extended bindings, and executed with a minimum heap size of at least ~6MB? Just to address a thought, and not because it would be needed for what I personally do or anything like that, on the possibility of GMP support for Gambit: it could potentially be added as a plugin/path, however: As I got it, GMP does not support using a custom memory allocator, and also its structures have internal pointers between each others, so GMP user code cannot move around GMP-allocated memory blocks. Presuming that this understanding is correct, it's like a compromised thing because using it in Gambit would imply a memory fragmentation-inducing mechanism at a basal language layer, which would at least theoretically be complete crap, and I'd guess these two points constitute such a big problem that the GMP guys should address it really. Apart from being a large, separate code library project which implies some limitation of usability in some sense, GMP's license is LGPL so it comes with some quirks that at least hypothethically could be major for some uses. I guess if the two tech issues with GMP were resolved, it could be interesting for someone to implement a GMP support patch for Gambit. What's the scope of use of GMP in Python and in a hypothetical Gambit GMP support patch, only integer bignums? If you have any thought on this feel free to share. In all cases it's awesome that Gambit bundles its own bignum logics as by that Gambit is without any dependency requirement and thus makes Gambit completely portable and self-sustaining. Best regards, Mikael 2013/6/7 Bradley Lucier <lucier@math.purdue.edu>
Bakul Shah wrote a particularly elegant Scheme program for Chudnovskys' algorithm for pi based on the Common Lisp program here:
https://bitbucket.org/**tarballs_are_good/numericl/**src/** 5fe8fe7089f48ab1c8a388632f815f**c35b4dec7e/src/experimental/** pi-chudnovsky.lisp?at=default<https://bitbucket.org/tarballs_are_good/numericl/src/5fe8fe7089f48ab1c8a388632f815fc35b4dec7e/src/experimental/pi-chudnovsky.lisp?at=default>
Nick Craig-Wood wrote a Python program using the GMP multiprecision library that appears to use exactly the same algorithm here:
I modified both programs a bit and include them here.
They time the calculation of $10^n$ digits of pi for $n=1,2,3,4,5,6,7$. The results are
heine:~/programs/gambiteer/**gambit> !py python pi_chudnovsky_bs_gmpy.py 314159265358979323846264338327**950288419716939937510582097494** 459230781640628620899862803482**53421170679 ('chudnovsky_gmpy_mpz_bs: digits', 10, 'time', 1.0967254638671875e-05) ('chudnovsky_gmpy_mpz_bs: digits', 100, 'time', 3.0040740966796875e-05) Last 5 digits 70679 OK ('chudnovsky_gmpy_mpz_bs: digits', 1000, 'time', 0.00025582313537597656) Last 5 digits 01989 OK ('chudnovsky_gmpy_mpz_bs: digits', 10000, 'time', 0.00386810302734375) Last 5 digits 75678 OK ('chudnovsky_gmpy_mpz_bs: digits', 100000, 'time', 0.0834801197052002) Last 5 digits 24646 OK ('chudnovsky_gmpy_mpz_bs: digits', 1000000, 'time', 1.655979871749878) Last 5 digits 58151 OK ('chudnovsky_gmpy_mpz_bs: digits', 10000000, 'time', 30.67442488670349) Last 5 digits 55897 OK heine:~/programs/gambiteer/**gambit> gsi chud1.scm 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: .004. Last 5 digits 1989. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000, CPU time: .028. Last 5 digits 75678. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000, CPU time: .472. Last 5 digits 24646. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000, CPU time: 6.448. Last 5 digits 58151. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000000, CPU time: 98.612. Last 5 digits 55897.
So it appears that for this algorithm applied to large integers, GMP's bignum routines are about 3-4 times as fast as Gambit's bignum routines. Not so bad. For smaller bignums, GMP has a bigger advantage.
The C program gmp-chudnovsky.c includes certain optimizations to this basic algorithm:
http://gmplib.org/pi-with-gmp.**html <http://gmplib.org/pi-with-gmp.html> ftp://ftp.gmplib.org/pub/misc/**gmp-chudnovsky.c<ftp://ftp.gmplib.org/pub/misc/gmp-chudnovsky.c>
On my machine, compiled with
gcc -O3 -march=native -o gmp-chudnovsky gmp-chudnovsky.c -lgmp -lm
the CPU times for 1,000,000 and 10,000,000 digits are 1.064 and 18.200 seconds, respectively.
This is with a somewhat older machine
model name : Intel(R) Core(TM)2 Quad CPU Q8200 @ 2.33GHz
running Ubuntu 13.04 with
heine:~/programs/gambiteer/**gambit> gcc -v Using built-in specs. COLLECT_GCC=gcc COLLECT_LTO_WRAPPER=/usr/lib/**gcc/x86_64-linux-gnu/4.7/lto-**wrapper Target: x86_64-linux-gnu Configured with: ../src/configure -v --with-pkgversion='Ubuntu/**Linaro 4.7.3-1ubuntu1' --with-bugurl=file:///usr/**share/doc/gcc-4.7/README.Bugs --enable-languages=c,c++,go,**fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.7 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/**include/c++/4.7 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --with-system-zlib --enable-objc-gc --with-cloog --enable-cloog-backend=ppl --disable-cloog-version-check --disable-ppl-version-check --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,**mx32 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu Thread model: posix gcc version 4.7.3 (Ubuntu/Linaro 4.7.3-1ubuntu1) heine:~/programs/gambiteer/**gambit> gsi -v v4.6.9 20130607151908 x86_64-unknown-linux-gnu "./configure '--enable-single-host' '--enable-multiple-versions' '--enable-shared'"
and the Ubuntu-provided GMP 5.0.5. (I'm sure the GMP folks have a better way to build GMP on my machine than the "generic" 64-bit version provided by Ubuntu.)
Brad
_______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On 06/07/2013 06:02 PM, Mikael wrote:
Was your Gambit pi-calculator compiled with (declare (not safe)) and any other related setting for optimizing speed, like increasing inlining, setting mostly generic and inlining standard and extended bindings, and executed with a minimum heap size of at least ~6MB?
The pi-calculator itself was interpreted; nearly all the work is done in the Gambit runtime library. I suppose compiling it did speed it up a bit: heine:~/programs/gambiteer/gambit> gsi chud1 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: .024. Last 5 digits 75678. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000, CPU time: .43200000000000005. Last 5 digits 24646. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000, CPU time: 6.151999999999999. Last 5 digits 58151. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000000, CPU time: 95.432.
What's the scope of use of GMP in Python and in a hypothetical Gambit GMP support patch, only integer bignums?
I don't know.
If you have any thought on this feel free to share.
In all cases it's awesome that Gambit bundles its own bignum logics as by that Gambit is without any dependency requirement and thus makes Gambit completely portable and self-sustaining.
Best regards, Mikael
2013/6/7 Bradley Lucier <lucier@math.purdue.edu <mailto:lucier@math.purdue.edu>>
heine:~/programs/gambiteer/gambit> gsi chud1.scm 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: .004. Last 5 digits 1989. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000, CPU time: .028. Last 5 digits 75678. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000, CPU time: .472. Last 5 digits 24646. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000, CPU time: 6.448. Last 5 digits 58151. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000000, CPU time: 98.612. Last 5 digits 55897.
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.
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
On 06/12/2013 01:20 PM, Marc Feeley wrote:
Are we close to setting a record?
No: http://bellard.org/pi/pi2700e9/pipcrecord.pdf http://www.numberworld.org/misc_runs/pi-10t/details.html Brad
On Wed, 12 Jun 2013 13:07:45 EDT Bradley Lucier <lucier@math.purdue.edu> wrote:
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.
This will help when you parallelize using GPUs! FFT multiplies on GPUs will not be able to handle very long numbers.
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!
Onion material but folks @ pcmag don't know it! They seem to have gotten the wrong end of the stick. I followed the chain and I think they are talking about what is reported here: http://carma.newcastle.edu.au/jon/bbp-bluegene.pdf or may be an earlier article on the same. This paper is much more interesting!
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 1000000000, CPU time: 41907.731069. Last 5 digits 45519.
Quite impressive! For comparison, gmp-chudnovksy.c does a million digits in 0.61s on 3.6Ghz 8core AMD FX, and 11 seconds on a 700Mhz RaspberryPi! For a billion digits it takes 2493 seconds. chud2 / gmp-chudnovsky ratio of about of 8 (@ 10^6 digits) and 16 (@ 10^9 digits) is most due to the fact that for big nums gmp has processor specific optimized assmebly code. And gambit uses double the space due to portable C code. Right there you lose a factor of two! The current record is 10 trillion (10^13) digits of pi. You'd need more than a single 2TB disk to store one such 10^13 digit number! Any arithmetic operation on such large numbers is essentially an exercise in streaming disks. And to do so efficiently you'd need some IO parallelism! To allow such things you'd need some sort of pluggable bignum architecture.
What is the time complexity of the Chudnovsky algorithm? On Wed, Jun 12, 2013 at 6:06 PM, Bakul Shah <bakul@bitblocks.com> wrote:
On Wed, 12 Jun 2013 13:07:45 EDT Bradley Lucier <lucier@math.purdue.edu> wrote:
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.
This will help when you parallelize using GPUs! FFT multiplies on GPUs will not be able to handle very long numbers.
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!
Onion material but folks @ pcmag don't know it! They seem to have gotten the wrong end of the stick. I followed the chain and I think they are talking about what is reported here: http://carma.newcastle.edu.au/jon/bbp-bluegene.pdf or may be an earlier article on the same. This paper is much more interesting!
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 1000000000, CPU time: 41907.731069. Last 5 digits 45519.
Quite impressive!
For comparison, gmp-chudnovksy.c does a million digits in 0.61s on 3.6Ghz 8core AMD FX, and 11 seconds on a 700Mhz RaspberryPi! For a billion digits it takes 2493 seconds.
chud2 / gmp-chudnovsky ratio of about of 8 (@ 10^6 digits) and 16 (@ 10^9 digits) is most due to the fact that for big nums gmp has processor specific optimized assmebly code. And gambit uses double the space due to portable C code. Right there you lose a factor of two!
The current record is 10 trillion (10^13) digits of pi. You'd need more than a single 2TB disk to store one such 10^13 digit number! Any arithmetic operation on such large numbers is essentially an exercise in streaming disks. And to do so efficiently you'd need some IO parallelism!
To allow such things you'd need some sort of pluggable bignum architecture. _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On Wed, 12 Jun 2013 22:05:20 CDT Phil Bewig <pbewig@gmail.com> wrote:
What is the time complexity of the Chudnovsky algorithm?
I don't really know. On a quick search I didn't find anything but I suspect it is dominated by the multiplication cost. The Schnhage-Strassen multiplication algorithm (using FFT) has a complexity of O(N log N log log N),where N is the length of the number. To get an idea we can compute the ratio of time cost for 10N and N. For N = 1000000 it is 12.9 and N = 10^7 it is about 12. Empirically it is 15.8 in Brad's tests and 16.3 for gmp-chudnovksy.c (10 seconds for 10^7, 163 seconds for 10^8). Between 10^8 & 10^9 Brad had to use Karatsuba and the ratio went up to about 32. It probably wouldn't be hard to figure out the number of additions, multiplications etc. as a function of how many terms are being evaluated. Each term adds a little over 14 digits. From that you can derive the compexity figure. Another interesting fact will be the memory traffic as a function of N! This can also be useful in gauging the effectiveness of any parallelizing.
2013/6/13 Bakul Shah <bakul@bitblocks.com> ..
chud2 / gmp-chudnovsky ratio of about of 8 (@ 10^6 digits) and 16 (@ 10^9 digits) is most due to the fact that for big nums gmp has processor specific optimized assmebly code. And
gambit uses double the space due to portable C code. Right there you lose a factor of two!
Wait, double space for what, and by what reason? Mikael
On Thu, 13 Jun 2013 10:09:09 +0300 Mikael <mikael.rcv@gmail.com> wrote:
gambit uses double the space due to portable C code. Right there you lose a factor of two!
Wait, double space for what, and by what reason?
You break up a bignum in "digits" & that you store one digit per word. I was told that in gambit the digit size is 32bits on a 64bit machine and 16its on a 32bit machine so you are fetching/storing at least 2N bits for an N bit bignum. As to why, you have to ask Gambit's bignum implementor. My guess is it makes certain operations easier in a higher level language that doesn't have operators for add-with-carry, returning double width results etc.
On 2013-06-13, at 12:12 PM, Bakul Shah <bakul@bitblocks.com> wrote:
On Thu, 13 Jun 2013 10:09:09 +0300 Mikael <mikael.rcv@gmail.com> wrote:
gambit uses double the space due to portable C code. Right there you lose a factor of two!
Wait, double space for what, and by what reason?
You break up a bignum in "digits" & that you store one digit per word. I was told that in gambit the digit size is 32bits on a 64bit machine and 16its on a 32bit machine so you are fetching/storing at least 2N bits for an N bit bignum.
As to why, you have to ask Gambit's bignum implementor. My guess is it makes certain operations easier in a higher level language that doesn't have operators for add-with-carry, returning double width results etc.
Brad, correct me if I'm wrong, but the bignum "digits" are stored in as many bytes as their precision. So there is no "factor of 2" here. Marc
On 06/13/2013 03:12 PM, Bakul Shah wrote:
On Thu, 13 Jun 2013 10:09:09 +0300 Mikael <mikael.rcv@gmail.com> wrote:
gambit uses double the space due to portable C code. Right there you lose a factor of two! Wait, double space for what, and by what reason? You break up a bignum in "digits" & that you store one digit per word. I was told that in gambit the digit size is 32bits on a 64bit machine and 16its on a 32bit machine so you are fetching/storing at least 2N bits for an N bit bignum.
As to why, you have to ask Gambit's bignum implementor. My guess is it makes certain operations easier in a higher level language that doesn't have operators for add-with-carry, returning double width results etc.
The bits of a bignum are contiguous, there is no empty space in a bignum. Bignums are stored in a twos-complement representation. Just as for Larceny, the Gambit bignum implementation was inspired by the paper Jon L White, Reconfigurable, Retargetable Bignums: A Case Study in Efficient, Portable Lisp System Building, Proceedings of the ACM conference on Lisp & FP, 1986. The string of bits in a bignum are conceptually divided into unsigned specialized "digits" of different sizes depending on their use. In Gambit, there are "adigits", used for addition, subtraction, shifting, and the bitwise-* operations. These are the largest available C numeric type, so if 64-bit "long long" is available, then that's the width of an "adigit" even if Scheme words are 32 bits. (I think one can configure Gambit to use 32-bit "adigits" on a 64-bit machine, but I don't see any reason to do so.) There are also "mdigits", used in the naive multiplication and division algorithms. For algorithmic reasons, an mdigit must be representable as a fixnum, so they're 16 bits on a 32-bit machine and 32 bits on a 64-bit machine. There are lots of other routines that use mdigits precisely because they do fit into a fixnum. Finally, there are "fdigits" used in the FFT-based multiplication routines. Right now, these are always 8 bits wide. The primitive operations, which are implemented as C macros in gambit.h, are taken from _num.scm and listed after the signature. I sent a patch to the Gambit mail list in 2009 that documents a bit more of this in _num.scm, but it was never applied: https://mercure.iro.umontreal.ca/pipermail/gambit-list/2009-September/004020... Brad (define-prim (##bignum.negative? x)) (define-prim (##bignum.adigit-length x)) (define-prim (##bignum.adigit-inc! x i)) (define-prim (##bignum.adigit-dec! x i)) (define-prim (##bignum.adigit-add! x i y j carry)) (define-prim (##bignum.adigit-sub! x i y j borrow)) (define-prim (##bignum.mdigit-length x)) (define-prim (##bignum.mdigit-ref x i)) (define-prim (##bignum.mdigit-set! x i mdigit)) (define-prim (##bignum.mdigit-mul! x i y j multiplier carry)) (define-prim (##bignum.mdigit-div! x i y j quotient borrow)) (define-prim (##bignum.mdigit-quotient u j v_n-1)) (define-prim (##bignum.mdigit-remainder u j v_n-1 q-hat)) (define-prim (##bignum.mdigit-test? q-hat v_n-2 r-hat u_j-2)) (define-prim (##bignum.adigit-ones? x i)) (define-prim (##bignum.adigit-zero? x i)) (define-prim (##bignum.adigit-negative? x i)) (define-prim (##bignum.adigit-= x y i)) (define-prim (##bignum.adigit-< x y i)) (define-prim (##bignum.->fixnum x)) (define-prim (##bignum.<-fixnum x)) (define-prim (##bignum.adigit-shrink! x n)) (define-prim (##bignum.adigit-copy! x i y j)) (define-prim (##bignum.adigit-cat! x i hi j lo k divider)) (define-prim (##bignum.adigit-bitwise-and! x i y j)) (define-prim (##bignum.adigit-bitwise-ior! x i y j)) (define-prim (##bignum.adigit-bitwise-xor! x i y j)) (define-prim (##bignum.adigit-bitwise-not! x i)) (define-prim (##bignum.fdigit-length x)) (define-prim (##bignum.fdigit-ref x i)) (define-prim (##bignum.fdigit-set! x i fdigit))
+1 for including the documentation patch, or 2013/6/14 Bradley Lucier <lucier@math.purdue.edu>
I sent a patch to the Gambit mail list in 2009 that documents a bit more of this in _num.scm, but it was never applied:
https://mercure.iro.umontreal.**ca/pipermail/gambit-list/2009-** September/004020.html<https://mercure.iro.umontreal.ca/pipermail/gambit-list/2009-September/004020.html>
Brad
On 06/12/2013 01:07 PM, Bradley Lucier 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 ...
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.
This is the same program, run on my new desktop: model name : Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz with 16GB of RAM, which seems to run 2-3 times as fast as the server in the math department. (Luckily, a new server will be up and running soon.) Brad firefly:~/programs/gambiteer> 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: .012. Last 5 digits 75678. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000, CPU time: .172. Last 5 digits 24646. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000, CPU time: 2.476. Last 5 digits 58151. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000000, CPU time: 38.7. Last 5 digits 55897. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000000, CPU time: 536.864. Last 5 digits 51592. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000000, CPU time: 14459.672. Last 5 digits 45519.
On Wed, Jul 10, 2013 at 11:47:48AM -0400, Bradley Lucier wrote:
On 06/12/2013 01:07 PM, Bradley Lucier 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 ...
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.
This is the same program, run on my new desktop:
model name : Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz
with 16GB of RAM, which seems to run 2-3 times as fast as the server in the math department. (Luckily, a new server will be up and running soon.)
Brad
firefly:~/programs/gambiteer> 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: .012. Last 5 digits 75678. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000, CPU time: .172. Last 5 digits 24646. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000, CPU time: 2.476. Last 5 digits 58151. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000000, CPU time: 38.7. Last 5 digits 55897. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000000, CPU time: 536.864. Last 5 digits 51592. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000000, CPU time: 14459.672. Last 5 digits 45519.
I'm an old-timer. I remember in the 60's when someone had calculated the first million digits off pi and offered to sell them on a reel of magnetic tape. I was impressed. Though not having a magnetic tape reader, and not needing more than the first five or so digits, I didn't take up the offer. Thhe did say they hadn't found seven consecutive 7's in those million digits, though. Is it now faster to calculate them than to download them? -- hendrik
_______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On Wed, Jul 10, 2013 at 11:47:48AM -0400, Bradley Lucier wrote:
This is the same program, run on my new desktop:
model name : Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz
with 16GB of RAM, which seems to run 2-3 times as fast as the server in the math department. (Luckily, a new server will be up and running soon.)
...
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000000, CPU time: 14459.672. Last 5 digits 45519.
Neat! On Wed, 10 Jul 2013 14:28:48 EDT Hendrik Boom <hendrik@topoi.pooq.com> wrote:
Is it now faster to calculate them than to download them?
A C version of the same algorithm takes about 40 minutes (on an 3.6Ghz AMD FX with 16GB). If you have an internet link that can sustain 417KB/s you can download faster :-)
From earlier in this thread: On Wed, 12 Jun 2013 22:25:15 PDT Bakul Shah <bakul@bitblocks.com> wrote: On Wed, 12 Jun 2013 22:05:20 CDT Phil Bewig <pbewig@gmail.com> wrote:
What is the time complexity of the Chudnovsky algorithm?
... It probably wouldn't be hard to figure out the number of additions, multiplications etc. as a function of how many terms are being evaluated.
I had measured these a while ago:
(test 1000000) 1000000: 211545 +, 356108 -, 775665 *, 141030 quotients
Roughly: 21% adds 36% subtracts 77% multiplies 14% quotients These counts scale linearly. -- Bakul chud-test.scm: (define _* *) (define _+ +) (define _- -) (define _quotient quotient) (define +count 0) (define -count 0) (define *count 0) (define qcount 0) (set! + (lambda x (set! +count (_+ 1 +count)) (apply _+ x))) (set! - (lambda x (set! -count (_+ 1 -count)) (apply _- x))) (set! * (lambda x (set! *count (_+ 1 *count)) (apply _* x))) (set! quotient (lambda x (set! qcount (_+ 1 qcount)) (apply _quotient x))) (define (pi digits) (let* ((A 13591409) (B 545140134) (C 640320) (C^3 (expt 640320 3)) (D 12)) (define (split m n) (if (= 1 (- n m)) (let ((g (* (- (* 6 n) 5) (- (* 2 n) 1) (- (* 6 n) 1)))) (list g (quotient (* C^3 (expt n 3)) 24) (* (expt -1 n) g (+ (* n B) A)))) (let* ((mid (quotient (+ m n) 2)) (gpq1 (split m mid)) (gpq2 (split mid n)) (g1 (car gpq1)) (p1 (cadr gpq1)) (q1 (caddr gpq1)) (g2 (car gpq2)) (p2 (cadr gpq2)) (q2 (caddr gpq2))) (list (* g1 g2) (* p1 p2) (+ (* q1 p2) (* q2 g1)))))) (let* ((num-terms (inexact->exact (floor (+ 2 (/ digits 14.181647462))))) (sqrt-C (integer-sqrt (* C (expt 100 digits)))) (gpq (split 0 num-terms)) (g (car gpq)) (p (cadr gpq)) (q (caddr gpq))) (quotient (* p C sqrt-C) (* D (+ q (* p A))))))) (define (print . x) (for-each display x)) (define (test count) (set! +count 0) (set! -count 0) (set! *count 0) (set! qcount 0) (pi count) (print count ": " +count " +, " -count " -, " *count " *, " qcount " quotients\n"))
On Jul 10, 2013, at 11:47 AM, Bradley Lucier <lucier@math.purdue.edu<mailto:lucier@math.purdue.edu>> wrote: On 06/12/2013 01:07 PM, Bradley Lucier 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 ... 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. This is the same program, run on my new desktop: model name : Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz with 16GB of RAM, which seems to run 2-3 times as fast as the server in the math department. (Luckily, a new server will be up and running soon.) Brad firefly:~/programs/gambiteer> 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: .012. Last 5 digits 75678. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000, CPU time: .172. Last 5 digits 24646. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000, CPU time: 2.476. Last 5 digits 58151. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000000, CPU time: 38.7. Last 5 digits 55897. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000000, CPU time: 536.864. Last 5 digits 51592. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000000, CPU time: 14459.672. Last 5 digits 45519. A new run on a MacBook Pro with M1 Ultra (64GB memory) on one processor: [MacBook-Pro:~/programs/gambit] lucier% gsi -:m1000000 chud1 Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10, CPU time: 1.419999999999963e-4. Last 5 digits 26535. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100, CPU time: 7.099999999999815e-5. Last 5 digits 70679. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000, CPU time: 6.139999999999965e-4. Last 5 digits 1989. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000, CPU time: .018569000000000002. Last 5 digits 75678. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000, CPU time: .123237. Last 5 digits 24646. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000, CPU time: 1.440205. Last 5 digits 58151. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000000, CPU time: 21.505972999999997. Last 5 digits 55897. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000000, CPU time: 294.886941. Last 5 digits 51592. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000000, CPU time: 7714.255436. Last 5 digits 45519. [MacBook-Pro:~/programs/gambit] lucier% gsi -v v4.9.4-30-g4c9a0bc3 20220331205952 arm-apple-darwin21.2.0 "./configure 'CC=gcc-11' '--enable-single-host' '--enable-march=native' '--enable-multiple-versions' '--enable-shared' '--enable-dynamic-clib'" So, it’s almost twice as fast as the 2013 i7-4770 (which was a sweet spot in historical Intel processor design in my opinion). I’ll include the program here just for info. Brad
On Apr 7, 2022, at 8:32 PM, Lucier, Bradley J <lucier@purdue.edu<mailto:lucier@purdue.edu>> wrote: A new run on a MacBook Pro with M1 Ultra (64GB memory) on one processor: Sorry, an M1 Max. (Who can keep track of Apple’s naming conventions?) Brad
participants (7)
-
Bakul Shah -
Bradley Lucier -
Hendrik Boom -
Lucier, Bradley J -
Marc Feeley -
Mikael -
Phil Bewig