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]
I’m in the process of implementing the --enable-path-encoding=X configuration option to allow the selection of a character encoding for filesystem paths. It will be possible to chose between native, latin1, utf8, ucs2, ucs4 and wchar. The current default is “native” and this will be changed to “utf8” which seems to be becoming the standard for filesystems.
Does anyone see a problem with this?
Note that the default character encoding for text files is ISO-8859-1 (latin1). Through the -:fX …
[View More]runtime option it is possible to select a default encoding different from the builtin default with the following choices: ASCII, ISO-8859-1, UCS-2, UCS-4, UTF-16, UTF-8 and UTF.
I’m considering adding a configuration option to change the builtin default character encoding for text files. What should the default default be? It is probably safest to keep ISO-8859-1 because it has a one to one mapping of bytes to characters. Comments?
Marc
[View Less]
======================================================================
CALL FOR PAPERS
WGP 2015
11th ACM SIGPLAN Workshop on Generic Programming
Vancouver, Canada
Sunday, August 30, 2015
http://www.wgp-sigplan.org/2015
Co-located with the
International Conference on Functional Programming (ICFP 2015)
========================================================…
[View More]==============
Goals of the workshop
---------------------
Generic programming is about making programs more adaptable by making
them more general. Generic programs often embody non-traditional kinds
of polymorphism; ordinary programs are obtained from them by suitably
instantiating their parameters. In contrast with normal programs, the
parameters of a generic program are often quite rich in structure; for
example they may be other programs, types or type constructors, class
hierarchies, or even programming paradigms.
Generic programming techniques have always been of interest, both to
practitioners and to theoreticians, and, for at least 20 years,
generic programming techniques have been a specific focus of research
in the functional and object-oriented programming communities. Generic
programming has gradually spread to more and more mainstream
languages, and today is widely used in industry. This workshop brings
together leading researchers and practitioners in generic programming
from around the world, and features papers capturing the state of the
art in this important area.
We welcome contributions on all aspects, theoretical as well as
practical, of
* generic programming,
* programming with (C++) concepts,
* meta-programming,
* programming with type classes,
* programming with modules,
* programming with dependent types,
* type systems for generic programming,
* polytypic programming,
* adaptive object-oriented programming,
* component-based programming,
* strategic programming,
* aspect-oriented programming,
* family polymorphism,
* object-oriented generic programming,
* implementation of generic programming languages,
* static and dynamic analyses of generic programs,
* and so on.
Program Committee
-----------------
* Patrick Bahr (co-chair), University of Copenhagen
* Sebastian Erdweg (co-chair), Technical University of Darmstadt
* Edwin Brady, University of St Andrews
* Edsko de Vries, Well-Typed LLP
* Mauro Jaskelioff, National University of Rosario
* Johan Jeuring, Utrecht University
* Pieter Koopman, Radboud University Nijmegen
* Bruno C. d. S. Oliveira, University of Hong Kong
* Nicolas Pouillard, IT University of Copenhagen
* Sukyoung Ryu, Korea Advanced Institute of Science and Technology
* Sibylle Schupp, Hamburg University of Technology
* Sam Tobin-Hochstadt, Indiana University
Proceedings and Copyright
-------------------------
We plan to have formal proceedings, published by the ACM. Accepted
papers will be included in the ACM Digital Library. Authors must grant
ACM publication rights upon acceptance
(http://authors.acm.org/main.html), but may retain copyright if they
wish. Authors are encouraged to publish auxiliary material with their
paper (source code, test data, and so forth). The proceedings will be
freely available for download from the ACM Digital Library from one
week before the start of the conference until two weeks after the
conference.
Submission details
------------------
* Submission deadline: Fri, 15th May 2015
* Author notification: Fri, 26th June 2015
* Final version due: Sun, 19th July 2015
* Workshop: Sun, 30th August 2015
Submitted papers should fall into one of two categories:
* Regular research papers (12 pages)
* Short papers: case studies, tool demos, generic pearls (6 pages)
Regular research papers are expected to present novel and interesting
research results. Short papers need not present novel or fully polished
results. Good candidates for short papers are those that report on
interesting case studies of generic programming in open source or
industry, present demos of generic programming tools or libraries,
or discuss elegant and illustrative uses of generic programming ('pearls').
All submissions should be in portable document format (PDF), formatted
using the ACM SIGPLAN style guidelines (two-column, 9pt). Regular
research papers must not exceed 12 pages. Short papers must not exceed
6 pages. If applicable, papers should be marked with one of the labels
'case study, 'tool demo' or 'generic pearl' in the title at the time
of submission.
Papers should be submitted via HotCRP at
https://icfp-wgp15.hotcrp.com/
Travel Support
--------------
Student attendees with accepted papers can apply for a SIGPLAN PAC grant
to help cover travel expenses. PAC also offers other support, such as
for child-care expenses during the meeting or for travel costs for
companions of SIGPLAN members with physical disabilities, as well as for
travel from locations outside of North America and Europe. For details
on the PAC program, see its web page (http://www.sigplan.org/PAC.htm).
History of the Workshop on Generic Programming
----------------------------------------------
Earlier Workshops on Generic Programming have been held in
* Gothenburg, Sweden 2014 (affiliated with ICFP),
* Boston, Massachusetts, US 2013 (affiliated with ICFP),
* Copenhagen, Denmark 2012 (affiliated with ICFP),
* Tokyo, Japan 2011 (affiliated with ICFP),
* Baltimore, Maryland, US 2010 (affiliated with ICFP),
* Edinburgh, UK 2009 (affiliated with ICFP),
* Victoria, BC, Canada 2008 (affiliated with ICFP),
* Portland 2006 (affiliated with ICFP),
* Ponte de Lima 2000 (affiliated with MPC),
* Marstrand 1998 (affiliated with MPC).
Furthermore, there were a few informal workshops
* Utrecht 2005 (informal workshop),
* Dagstuhl 2002 (IFIP WG2.1 Working Conference),
* Nottingham 2001 (informal workshop).
There were also (closely related) DGP workshops in Oxford (June
3-4 2004), and a Spring School on DGP in Nottingham (April 24-27
2006, which had a half-day workshop attached).
WGP Steering Committee
----------------------
* Andres Löh
* Ronald Garcia
* Jacques Carette
* Jeremiah Willcock
* José Pedro Magalhães
* Tiark Rompf
* Tarmo Uustalo
* Stephanie Weirich
* Fritz Henglein
_______________________________________________
Agda mailing list
Agda(a)lists.chalmers.se
https://lists.chalmers.se/mailman/listinfo/agda
[View Less]
Call For Papers:
Scheme and Functional Programming Workshop 2015
Vancouver, British Columbia, Canada
(Co-located with ICFP 2015)
http://andykeep.com/SchemeWorkshop2015/
========================================================================
Submissions related to Scheme, Racket, Clojure, and functional
programming are welcome and encouraged. Topics of interest include
but are not limited to:
* Program-development environments, debugging, testing
* Implementation (interpreters, …
[View More]compilers, tools, benchmarks, etc.)
* Syntax, macros, hygiene
* Distributed computing, concurrency, parallelism
* Interoperability with other languages, FFIs
* Continuations, modules, object systems, types
* Theory, formal semantics, correctness
* History, evolution and standardization of Scheme
* Applications, experience and industrial uses of Scheme
* Education
* Scheme pearls (elegant, instructive uses of Scheme)
We also welcome submissions related to dynamic or multiparadigmatic
languages and programming techniques.
========================================================================
Important Dates:
May 22nd, 2015 - Paper deadline
June 26th, 2015 - Author notification
July 19th, 2015 - Camera-ready deadline
September 4th, 2015 - Workshop
========================================================================
Submissions must be in ACM proceedings format, no smaller than 9-point
type (10-point type preferred). Microsoft Word and LaTeX templates for
this format are available at:
http://www.acm.org/sigs/sigplan/authorInformation.htm
Submissions should be in PDF and printable on US Letter.
To encourage authors to submit their best work, this year we are
encouraging shorter papers (around 6 pages, excluding references). This
is to allow authors to submit longer, revised versions of their papers
to archival conferences or journals. Longer papers (10--12 pages) are
also acceptable, if the extra space is needed. There is no maximum
length limit on submissions, but good submissions will likely be in the
range of 6 to 12 pages.
More information available at: http://andykeep.com/SchemeWorkshop2015/
========================================================================
Organizers:
Andy Keep, Cisco Systems Inc. (General Chair)
Ryan Culpepper, Northeastern University (Program Chair)
(Apologies for duplications from cross-posting.)
[View Less]
My youngest daughter thinks it would be cool to make some Gambit T-Shirts. She’s serious about her project and has made a Google Forms survey to figure out how many T-Shirts to make:
https://docs.google.com/forms/d/1W69hjwXe4EoMzWfZ9AhlkOHz0VOcg69BtnpwwzBglR…
This is just a survey… she will create the actual purchasing website later on.
Please fill the survey if you want to support her project and have an awesome shirt!
Marc
I discovered that github has a chatroom feature, so I have created one for Gambit. I have put a link on the Gambit wiki page, and one on the Gambit github repo. Here’s the link:
https://gitter.im/feeley/gambit
I hope it turns out to be a nice place for Gambit users to meet and exchange ideas.
Marc
Hi gambit users
I am trying to verify that a program written in Gambit-C scheme is as fast
as equivalent C program.
I tried to make a scheme version of the following C++ program which is;
*#include <iostream>*
*#include <cmath>*
*#include <cstdio>*
*#include <ctime>*
*#include <cstdlib>*
*#include <iomanip> *
*using namespace std;*
*double f(double x);*
*int main(int argc, char* argv[]) {*
* clock_t start;*
* start = clock();*
* double duration;*
* …
[View More]double sum = 0;*
* long n = atoi(argv[1]);*
* double x;*
* for(long i = 1; i <= n ;i++) {*
* x = (i - 0.5) / n;*
* sum += 4.0/(1.0+x*x);*
* }*
* sum /= n;*
* cout << setprecision(17) << sum << endl << endl;*
* duration = ( clock() - start ) / (double) CLOCKS_PER_SEC;*
* cout << duration <<'\n';*
* return 0;*
*}*
*double f(double x) {*
* return 4.0/(1.0 + x*x);*
*}*
and my best so far is
*#!/usr/bin/env gsi-script*
*(declare*
* (not safe)*
* (mostly-flonum))*
*(define (main arg)*
* (let ((k (string->number arg)))*
* (pretty-print (time (cpi (exact->inexact k))))))*
*(define (cpi n)*
* (letrec ((rec (lambda (i sum)*
* (let* ((x (fl/ (fl- i 0.5) n))*
* (summand (fl/ 4.0 (fl+ 1.0 (fl* x x)))))*
* (if (fl> i n)*
* (fl/ sum n)*
* (rec (fl+ i 1.0) (fl+ sum summand)))))))*
* (rec 0.0 0.0)))*
and the result is poor: 0.043s vs 0.145s
*server@HP-Proliant-MicroServer:~/speedtest$ ls*
*pi.cpp pi.scm*
*server@HP-Proliant-MicroServer:~/speedtest$ g++ -o pi-cpp pi.cpp*
*server@HP-Proliant-MicroServer:~/speedtest$ gsc -exe -o pi-scm pi.scm*
*server@HP-Proliant-MicroServer:~/speedtest$ time ./pi-cpp 1000000*
*3.1415926535897643*
*0.038903*
*real 0m0.043s*
*user 0m0.042s*
*sys 0m0.004s*
*server@HP-Proliant-MicroServer:~/speedtest$ time ./pi-scm 1000000*
*(time (cpi (exact->inexact k)))*
* 128 ms real time*
* 128 ms cpu time (127 user, 2 system)*
* 182 collections accounting for 67 ms real time (72 user, 1 system)*
* 224000448 bytes allocated*
* 341 minor faults*
* no major faults*
*3.1415966535897644*
*real 0m0.145s*
*user 0m0.136s*
*sys 0m0.009s*
*server@HP-Proliant-MicroServer:~/speedtest$ *
So.. I guess my scheme version is not equivalent to the original C++
program,
but I'm having trouble figuring out why
any help will be appreciated
any comment, any suggestion..
[View Less]