Hi Bradley,
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/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:
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
_______________________________________________
Gambit-list mailing list
Gambit-list@iro.umontreal.ca
https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list