[gambit-list] Gambit versus Python+GMP: Timing for Chudnovskys' algorithm for pi

Bradley Lucier lucier at math.purdue.edu
Fri Jun 7 15:38:23 EDT 2013


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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: gmp-chudnovsky.c
Type: text/x-csrc
Size: 16191 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20130607/3415e758/attachment.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: chud1.scm
Type: text/x-scheme
Size: 1813 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20130607/3415e758/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pi_chudnovsky_bs_gmpy.py
Type: text/x-python
Size: 2772 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20130607/3415e758/attachment.py>


More information about the Gambit-list mailing list