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/5fe8fe7089f48ab1c8a388…
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 …
[View More]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.htmlftp://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
[View Less]
Dear Marc,
I am sending over an u8vector from the Scheme world to the C world.
Of course the u8vector must be still, so that its heap allocated object's
memory address is not moved by Gambit's memory system.
To get clear on this topic, I have three quick questions for you:
(1) I see there's the function |##still-copy| in Gambit's runtime.
Browsing its code I don't see the keyword ___STILL mentioned anywhere in
it. How does it get the ___STILL property, is that an implicit argument to
…
[View More]___alloc_scmobj ?
(2) Is |##still-copy| a "universal copier" of any heap allocated object,
into an equivalent of itself that is ___STILL, so I can use it for, say,
u32vector, floating point number, complex number, string, Scheme struct?
(3) Is there any checker in Gambit's runtime, e.g. a |##still?|, whereby I
can check if a heap allocated object is ___STILL already?
Your clarification is much appreciated, thanks!
Phil
[View Less]
Hi!
In C, I like to get the memory address (void*, char*, etc.) of the blob in
a Scheme u8vector. That is a u8vector that is _still_, of course. Also of
course this means a pointer to the first byte in the u8vector.
I see how to do it here
http://gambitscheme.org/wiki/index.php/Using_Gambit_with_External_Libraries…
, and there are multiple suggestions in there.
Of all the suggestions, the "void *u8vectorptr =
___CAST(void*,___BODY(u8v));" form is the shortest form.
The default recommended …
[View More]form however uses "___BODY_AS(u8v,___tSUBTYPED)"
instead of ___BODY. Another suggestion uses &___FETCH_U8(___arg1,0), or
instead of 0, ___INT(0).
Can you please explain, is there any material difference or advantage
between these?
Are they equal so all else the same, the shortest form I mentioned is the
preferable one?
Thanks,
Phil
[View Less]
SRFI 179: Nonempty Intervals and Generalized Arrays (Updated),
https://srfi.schemers.org/srfi-179/
an extension of SRFI 122, has been added as a module to LambdaNative,
which the developers describe as
LambdaNative is an open-source (BSD licensed) cross-platform development
environment written in Scheme (Gambit-C), supporting Android, iOS,
BlackBerry 10, OS X, Linux, Windows, OpenBSD, NetBSD, FreeBSD and OpenWrt.
https://www.lambdanative.org/https://github.com/part-cw/lambdanative…
[View More]LambdaNative is written in Gambit Scheme.
Brad
[View Less]