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

Mikael mikael.rcv at gmail.com
Fri Jun 7 18:02:44 EDT 2013


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 at 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:
>
> http://www.craig-wood.com/**nick/articles/pi-chudnovsky/<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
> 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 at iro.umontreal.ca
> https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20130608/4cb4d71d/attachment.htm>


More information about the Gambit-list mailing list