Octobre 2018 - Gambit-list - mailman.iro.umontreal.ca

Gambit versus Python+GMP: Timing for Chudnovskys' algorithm for pi
by Bradley Lucier 07 Avr '22

07 Avr '22

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 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

7 18

Updated fork of SRFI 122, Nonempty Intervals and Generalized Arrays
by Bradley Lucier 04 Déc '18

04 Déc '18

I maintain a fork of SRFI 122 https://github.com/gambiteer/srfi-122/ where I've added a few things that were not in the finalized SRFI, specifically the routines interval-cartesian-product array-outer-product array-assign! I continue to think about arrays and how to use them. I'd like to get various implementations and applications of SRFI-122 available (beyond what I use it for) and when it looks like I don't have anything more to add I might propose an updated SRFI with the new routines. In that vein, if anyone would like assistance to modify SRFI-122 to run in their favorite scheme, or to use SRFI-122 in support of their application, I'd be glad to help. Brad

3 6

Call For Workshop Proposals
by Sam Tobin-Hochstadt 29 Oct '18

29 Oct '18

CALL FOR WORKSHOP AND CO-LOCATED EVENT PROPOSALS ICFP 2019 24th ACM SIGPLAN International Conference on Functional Programming August 18 - 23, 2019 Berlin, Germany https://icfp19.sigplan.org/ The 24th ACM SIGPLAN International Conference on Functional Programming will be held in Berlin, Germany on August 18-23, 2019. ICFP provides a forum for researchers and developers to hear about the latest work on the design, implementations, principles, and uses of functional programming. Proposals are invited for workshops (and other co-located events, such as symposiums) to be affiliated with ICFP 2019 and sponsored by SIGPLAN. These events should be less formal and more focused than ICFP itself, include sessions that enable interaction among the attendees, and foster the exchange of new ideas. The preference is for one-day events, but other schedules can also be considered. The workshops are scheduled to occur on August 18th (the day before ICFP) and 22-23th of August (the two days after ICFP). ---------------------------------------------------------------------- Submission details Deadline for submission: November 25, 2018 Notification of acceptance: December 23, 2018 Prospective organizers of workshops or other co-located events are invited to submit a completed workshop proposal form in plain text format to the ICFP 2019 workshop co-chairs (Jennifer Hackett and Christophe Scholliers), via email to icfp-workshops-2019(a)googlegroups.com by November 25, 2018. (For proposals of co-located events other than workshops, please fill in the workshop proposal form and just leave blank any sections that do not apply.) Please note that this is a firm deadline. Organizers will be notified if their event proposal is accepted by December 23, 2018, and if successful, depending on the event, they will be asked to produce a final report after the event has taken place that is suitable for publication in SIGPLAN Notices. The proposal form is available at: http://www.icfpconference.org/icfp2019-files/icfp19-workshops-form.txt Further information about SIGPLAN sponsorship is available at: http://www.sigplan.org/Resources/Proposals/Sponsored/ ---------------------------------------------------------------------- Selection committee The proposals will be evaluated by a committee comprising the following members of the ICFP 2019 organizing committee, together with the members of the SIGPLAN executive committee. Workshop Co-Chair: Jennifer Hackett (University of Nottingham) Workshop Co-Chair: Christophe Scholliers (University of Ghent) General Chair: Derek Dreyer (MPI-SWS) Program Chair: François Potier (Inria) ---------------------------------------------------------------------- Further information Any queries should be addressed to the workshop co-chairs (Jennifer Hackett and Christophe Scholliers), via email to icfp-workshops-2019(a)googlegroups.com

1 0

define-syntax
by Steve Graham 26 Oct '18

26 Oct '18

gsi 4.8.9 does not seem to have this. Must I install this as an extra? Windows 10 system.

2 2

Scheme Workshop presentation
by Marc Feeley 16 Oct '18

16 Oct '18

For those who weren’t able to make it to the Scheme wokshop to hear the talk “Tail calling between C and Native backends”, which explains the approach used by Gambit to call between code generated by the C and native backend, the talk is now available on youtube here : https://www.youtube.com/watch?v=sRRmh4rZGOQ Marc

1 0

Native backend
by Marc Feeley 01 Oct '18

01 Oct '18

For those interested in how the native backend for Gambit is progressing, here are some links to the paper that was presented yesterday at the Scheme workshop, and the slides of the talk. Laurent Huberdeau did a great job! http://www.iro.umontreal.ca/~gambit/SW2018-talk.pdf https://www.brinckerhoff.org/scheme2018/papers/Huberdeau_Feeley.pdf Marc

3 3