May 2014 - Gambit-list - mailman.iro.umontreal.ca

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

07 Apr '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

object->u8vector as tree shaker?
by Bradley Lucier 29 Mar '15

29 Mar '15

Marc: It's not quite clear to me what object->u8vector does with procedures. I was thinking that if it pulled in all the functions not in system libraries, then it could be used as a tree-shaker. This is only a vague thought, but I find its interesting. Brad

3 6

Call for brains!
by Tomas Möre 25 May '14

25 May '14

Hello! If you feel like taking on a little challenge read on! I am currently working on a gambit UI kit that is containing glfw and OpenGL (It will be open source and free) It will also be native to gambit, so no weird hocus pokus required! Well a little bit of black magic and sacrificial of virgins is always needed to get things to run properly... (The result will hopefully be better then my so called jokes) Since modern OpenGL requires some hefty matrix math I need to make a matrix math library. Since I want this to be multi platform compatible and easy to use even in the interpreter. I have to do all this in scheme. (Except we're forced to allocate the the scheme binary vectors in c to make them not move during garbage collection) But back to business! I've made the following macro and procedure to test matrix multiplication (To test simply copy paste into interpreter) But as you will se on the test i've added on the last row of code this is a pretty "slow" procedure. The question is, How do you make this quicker? Thank you for reading this long! :) !!!! warning "ugly" code #######################CODE START############################ ;; because the multiplication of matricies require a ton of commands we make a macro! :D ;; the macro requires the nr of columns and the number of rows and the current position of both column and row (define-macro (f32-mat*-elem columns rows column-pos row-pos first-vector second-vector) (let ((result '())) (let loop ((i 0)) (set! result (cons `(##fl* (##f32vector-ref ,first-vector ,(fx+ row-pos i)) (##f32vector-ref ,second-vector ,(fx+ column-pos (* i columns))) ) result)) (if (not (eq? i rows)) (loop (+ i 1))) ) (set! result (reverse result)) `(##fl+ ,@result) )) ;; multiplies two matricites of the dimetions 4x4 into one (define (f32mat4* first-vector second-vector) (f32vector ;;-still (f32-mat*-elem 4 4 0 0 first-vector second-vector) (f32-mat*-elem 4 4 1 0 first-vector second-vector) (f32-mat*-elem 4 4 2 0 first-vector second-vector) (f32-mat*-elem 4 4 3 0 first-vector second-vector) (f32-mat*-elem 4 4 0 1 first-vector second-vector) (f32-mat*-elem 4 4 1 1 first-vector second-vector) (f32-mat*-elem 4 4 2 1 first-vector second-vector) (f32-mat*-elem 4 4 3 1 first-vector second-vector) (f32-mat*-elem 4 4 0 2 first-vector second-vector) (f32-mat*-elem 4 4 1 2 first-vector second-vector) (f32-mat*-elem 4 4 2 2 first-vector second-vector) (f32-mat*-elem 4 4 3 2 first-vector second-vector) (f32-mat*-elem 4 4 0 3 first-vector second-vector) (f32-mat*-elem 4 4 1 3 first-vector second-vector) (f32-mat*-elem 4 4 2 3 first-vector second-vector) (f32-mat*-elem 4 4 3 3 first-vector second-vector) )) (define x (f32vector 1. 2. 3. 4. 1. 2. 3. 4. 1. 2. 3. 4. 1. 2. 3. 4.)) (define y (f32vector 1. 2. 3. 4. 1. 2. 3. 4. 1. 2. 3. 4. 1. 2. 3. 4.)) (time (let loop ((i 1000)) (f32mat4* x y) (if (not (eq? i 0)) (loop (- i 1 ))))) ####################### CODE END ####################################

4 3

How read and understand the compiler sources i.e. gsc/*.scm ?
by Mikael 24 May '14

24 May '14

Dear Marc, For a layperson to read through the compiler's sources (i.e. gsc/*.scm) as to get a general understanding of its internal workings, would you suggest any particular reading order, be it sequential or parallell? Also, would there be any contextual understanding that would be particularly important to have - such as for instance, structural qualities to the code that, for a reader to make sense of them, he must have already a particular frame of reference? (to avoid 'saving an hour theory by spending a month in the lab'.) At its 41klocs, it would be feasible for a user to read all of it and actually get to a pretty good understanding! That appears to me like a worthy cause. Thanks! Mikael

1 0

Re: [gambit-list] Call for brains!
by Marijn Schouten (hkBst) 24 May '14

24 May '14

On 23-05-14 14:22, Tomas Möre wrote: > *Bradley*: > Thanks for showing this. Haven't seen that before. > I assume what I do is add the code into that page and run ./bench -r (some number) gambit "nucleic" > However I can not make sense of the result? > > (nucleic 0 0) > > What does the two numbers represent? > > Marijn: > Thank you for all the links. I will definitely go through them! > But I must ask what you mean by "first make it correct". Hi Tomas, by that I meant that the version you posted reads beyond the bounds of your matrices and doesn't warn about it because you're using unsafe functions. It's pretty meaningless to measure how fast you can compute an incorrect matrix product... Marijn

1 0

ffi object is calling twice
by emil brusic 20 May '14

20 May '14

Greetings to everybody! I have recently tried to use Gambit-C for interfacing OpenCascade (OCE) library which is written in C++. So, I am using Gambit-C based on g++ compiler. I have started with simple vector class i.e. gp_XY which has 2 members, x and y coordinate. >From OCE source: inline void gp_XY::Add (const gp_XY& Other) { x += Other.x; y += Other.y; } This is from my gpXY.scm : (##namespace ("oce-gp-xy#")) (##include "~~/lib/gambit#.scm") (declare (standard-bindings) (block)) (c-declare #<<c-declare-end #include <gp_XY.hxx> extern "C" { typedef struct h_gp_XY h_gp_XY; typedef struct h_gp_Mat2d h_gp_Mat2d; h_gp_XY* gp_XY_create() { return reinterpret_cast<h_gp_XY*>(new gp_XY()); } h_gp_XY* gp_XY_create_ff(const Standard_Real x,const Standard_Real y) { return reinterpret_cast<h_gp_XY*>(new gp_XY(x,y)); } void gp_XY_destroy(h_gp_XY* h) { delete reinterpret_cast<gp_XY*>(h); } void my_add(gp_XY& Me, const gp_XY& Other) { Me.SetX(Me.X() + Other.X()); Me.SetY(Me.Y() + Other.Y()); } } c-declare-end ) (c-define-type XY "h_gp_XY") (c-define-type XY* (pointer XY)) (c-define-type Mat2d "h_gp_Mat2d") (c-define-type Mat2d* (pointer Mat2d)) ... ; problem with add (define add (c-lambda (XY* XY*) void #<<c-lambda-end const gp_XY& other = *(reinterpret_cast<gp_XY*>(___arg2)); gp_XY* th = reinterpret_cast<gp_XY*>(___arg1); th->Add(other); ; reinterpret_cast<gp_XY*>(___arg1)->Add(other); c-lambda-end )) That file is compiled and linked with OCE libraries. And in gsi interpreter: > (load "gpXY") "/home/emil/projects/scheme/gambit/oce/c++/src/gpXY.o1" > (##include "gpXY#.scm") > (define p1 (create-ff 1.0 2.0)) > (define p2 (create-ff 10.0 5.0)) > (add p1 p2) > (x p1) 21. > (y p1) 12. Obviously there is bug somewhere, because results should be 11 and 7. So I wrote my_add function and it calculated add vector correctly. Is it something wrong in my code? I do not have experience in Gambit-C. Any help or hint will be appreciated. Regards, Emil

1 0

Glfw Bindings
by Tomas Möre 18 May '14

18 May '14

Hey, I just made GLFW bindings for gambit. Found here: https://github.com/black0range/gambit-GLFW Currently also working on a "schemified" version that removes all necessities for c pointers, structs etc. etc. Best, Tomas Möre

1 0

ICFP 2014 Student Research Competition: Call for Submissions
by David Van Horn 16 May '14

16 May '14

====================================================================== CALL FOR SUBMISSION SRC@ICFP 2014 Gothenburg, Sweden 1-3 September 2014 http://www.icfpconference.org/icfp2014/src.html Co-located with the International Conference on Functional Programming (ICFP 2014) ====================================================================== Student Research Competition ------------------------ This year ICFP will host a Student Research Competition where undergraduate and postgraduate students can present posters. The SRC at the ICFP 2014 consists of three rounds: Extended abstract round: All students are encouraged to submit an extended abstract outlining their research (800 words). Poster session at ICFP 2014: Based on the abstracts, a panel of judges will select the most promising entrants to participate in the poster session which will take place at ICFP. Students who make it to this round will be eligible for some travel support to attend the conference. In the poster session, students will have the opportunity to present their work to the judges, who will select three finalists in each category* (graduate/undergraduate) to advance to the next round. ICFP presentation: The last round will consist of an oral presentation at the ICFP to compete for the final awards in each category. Prizes ----- * Both the top three graduate and the top three undergraduate winners will receive prizes of $500, $300, and $200, respectively. * All six winners will receive award medals and a two-year complimentary ACM student membership, including a subscription to ACMâ€™s Digital Library. * The names of the winners will be posted on the SRC web site. * The overall first place winner of the SRC will be invited to participate in the ACM SRC Grand Finals, an on-line round of competitions among the winners of other conference-hosted SRCs. * Grand Finalists and their advisors will be invited to the Annual ACM Awards Banquet for an all-expenses-paid trip, where they will be recognized for their accomplishments along with other prestigious ACM award winners, including the winner of the Turing Award (also known as the Nobel Prize of Computing). * The top three graduate Grand Finalists will receive an additional $500, $300, and $200. Likewise, the top three undergraduate Grand Finalists will receive an additional $500, $300, and $200. All six Grand Finalists will receive Grand Finalist certificates. * The ACM, Microsoft Research, and our industrial partners provide financial support for students attending the SRC. You can find more information about this on the ACM website. Eligibility -------- The SRC is open to both undergraduate (not in a PhD programme) and graduate students (in a PhD programme). Upon submission, entrants must be enrolled as a student at their universities, and are ACM student members. Furthermore, there are some constraints on what kind of work may be submitted. Previously published work: Submissions should consist of original work (not yet accepted for publication). If the work is a continuation of previously published work, the submission should focus on the contribution over what has already been published. We encourage students to see this as an opportunity to get early feedback and exposure for the work they plan to submit to the next ICFP or POPL. Collaborative work: Students are encouraged to submit work they have been conducting in collaboration with others, including advisors, internship mentors, or other students. However, submissions are individual, so they must focus on the contributions of the student. Submission Details --------------- Each submission should include the student authorâ€™s name, institutional affiliation, e-mail address, and postal address; research advisorâ€™s name; ACM student member number; category (undergraduate or graduate); research title; and an extended abstract addressing the following: * Problem and Motivation: Clearly state the problem being addressed and explain the reasons for seeking a solution to this problem. * Background and Related Work: Describe the specialized (but pertinent) background necessary to appreciate the work. Include references to the literature where appropriate, and briefly explain where your work departs from that done by others. * Approach and Uniqueness: Describe your approach in attacking the problem and clearly state how your approach is novel. * Results and Contributions: Clearly show how the results of your work contribute to computer science and explain the significance of those results. The abstract must describe the studentâ€™s individual research and must be authored solely by the student. If the work is collaborative with others and/or part of a larger group project, the abstract should make clear what the studentâ€™s role was and should focus on that portion of the work. The extended abstract must not exceed 800 words and must not be longer than 2 pages. The reference list does not count towards these limits. To submit an abstract, please register through the submission page and follow the instructions. Abstracts submitted after the deadline may be considered at the committee's discretion, but only after decisions have been made on all abstracts submitted before the deadline. If you have any problems, don't hesitate to contact the competition chair. Important Dates ------------- * Deadline for submission: 29 June * Notification of acceptance: 14 July Selection Committee ---------------- Jeremy Gibbons, University of Oxford Andrew Kennedy, Microsoft Research Cambridge Matthieu Sozeau, INRIA Paris Sam Tobin-Hochstadt, Indiana University Meng Wang, Chalmers University of Technology (Chair) Stephanie Weirich, University of Pennsylvania Transport of your poster ------------------- You can either bring your poster on your own to the conference or mail it to the local organizers: Attn.: Meng Wang Chalmers University of Technology Department of Computer Science and Engineering SE-412 96 Göteborg, Sweden If you choose to mail, please make sure that the poster will arrive at the latest on 30th August 2014.

1 0

Javascript Backend
by Bob Coleman 16 May '14

16 May '14

Greetings, I have been playing around with the javascript backend and have been impressed with it's capabilities. Interacting with other javascript libraries is not a problem, but I haven't found a way for other javascript code to call scheme defined functions. Is there a way to define functions to be called by javascript similar to c-lambda or c-define? Also, is it possible to access the value of the -target flag in scheme? I would like to define some functions differently based on whether the program is being built for the C or javascript backend. Thanks for your help. Bob

3 7

no more unicode characters?
by Marijn Schouten (hkBst) 16 May '14

16 May '14

Hi, I'm getting this behavior: $ gsi Gambit v4.7.2 > #\à *** ERROR IN (console)(a)1.1 -- Invalid '#\' name: "\303\240" is that a misconfiguration on my part somehow? Marijn

4 6