GMP integration

Back in 2003 there was a flurry of Scheme implementations adopting/
integrating with the GMP libraries. Does anyone know what the current
state of play is on that topic?

david

Hi,

David Rush <kumoyuki@gmail.com> writes:

> Back in 2003 there was a flurry of Scheme implementations adopting/
> integrating with the GMP libraries. Does anyone know what the current
> state of play is on that topic?

GNU Guile 1.8 implements the full R5RS numeric tower using GMP.

Thanks,
Ludovic.

David Rush wrote:
> Back in 2003 there was a flurry of Scheme implementations adopting/
> integrating with the GMP libraries. Does anyone know what the current
> state of play is on that topic?

Ikarus uses GMP (the low-level mpn_* procedures) for some of its bignum
procedures (+, -, *, cmp, div, rem, mod, ->string, and integer-sqrt).
The rest of the numeric procedures don't use GMP directly.

David Rush wrote:
> Back in 2003 there was a flurry of Scheme implementations adopting/
> integrating with the GMP libraries. Does anyone know what the current
> state of play is on that topic?

I believe a number of Scheme implementations use GMP.
On top of my head without any fact checking:

Chicken Scheme
Gambit
Guile
Ikarus
Larceny
PLT Scheme

But using GMP is not always a good idea. Quoting
AUbrey Jaffer:

Numerical naivete apparently motivated developers of Guile, which is
descended from SCM, to replace SCM's integrated arithmetics with an
external package. Guile uses GNU MP:

I deleted all code belonging to the old bignum implementation and
replaced it with calls to some older GMP...

On my PII 266 with 64MB it now computes (factorial 10000) in about
two seconds, if no garbage collection occurs. If gc is activated
however, guile performs the calculation within 200KB and calls gc
several times. The whole thing takes about 25 seconds (!), but this
is still twice as fast as the old implementetation. (I do not
garantee for these figures).

(factorial 10000) is a 118459.bit number. Numbers that large are of
number-theoretical interest only. For example, secure encryption keys
are currently 1024 bits. Public keys 100 times wider would take 10000
times longer to compute; not practical for Internet shopping.

That such a large number was necessary for FFT multiplication to prevail
over O(b2) multiplication is high praise for the SCM implementation.


Reference:

http://swiss.csail.mit.edu/~jaffer/CNS/DIMPA.html

--
Jens Axel Søgaard

On Mar 27, 10:37 am, Jens Axel Soegaard <inva...@soegaard.net> wrote:
>
> That such a large number was necessary for FFT multiplication to prevail
> over O(b2) multiplication is high praise for the SCM implementation.
>

It's also more difficult to get correct.  The GMP front page has this
scary quote:

GMP is very often miscompiled!  We
are seeing ever increasing problems
with miscompilations of the GMP code.
It has now come to the point where a
compiler should be assumed to miscompile
GMP. Please never use your newly compiled
libgmp.a or libgmp.so without first
running make check.

Using a floating point FFT to implement integer multiplication is
sketchy.  Python's approach of using Karatsuba multiplication was a
good decision...

On Mar 27, 5:37 pm, Jens Axel Soegaard <inva...@soegaard.net> wrote:
> David Rush wrote: 
>
> I believe a number of Scheme implementations use GMP.
> On top of my head without any fact checking:
>
>    Chicken Scheme

I had no idea. I will definitely take a look.

>    Gambit

I'm pretty sure this is false.

>    Guile

I'd seen this from the 2003 c.l.s posts, and your citation below about
the performance level.

>    Ikarus

Which for some reason I can't manage to get the source code to
download from the bzr repository. It keeps getting stuck  "Copying
content texts 3/5".

>    Larceny

I'm pretty sure this is also false, although there may well be an FFI
package which uses it.

>    PLT Scheme

I'd also seen this from the 2003 work.

> But using GMP is not always a good idea.

Nolo contendre. But I am looking at performing some experiments with
novel representations of inexact numbers and I thought that a GMP-
based numerical tower would be easy for performing side-by-side
comparisons. Obviously, having a Scheme implementation substrate that
is relatively simple to work with is another important dimension to
this choice.

david rush

David Rush skrev:
> On Mar 27, 5:37 pm, Jens Axel Soegaard <inva...@soegaard.net> wrote: 
>
> I had no idea. I will definitely take a look.

http://chicken.wiki.br/gmp

> 
>
> I'm pretty sure this is false.

Indeed. (I think an old Gambit vs GMP benchmark  me).
 
>
> I'd seen this from the 2003 c.l.s posts, and your citation below about
> the performance level.
> 
>
> Which for some reason I can't manage to get the source code to
> download from the bzr repository. It keeps getting stuck  "Copying
> content texts 3/5".

Did you try to fetch the lightweight repository?
The full repository takes *ages* to fetch.
 
>
> I'm pretty sure this is also false, although there may well be an FFI
> package which uses it.

If the 1998 note still is correct, then Larceny has its own
bignum implementation.

http://www.ccs.neu.edu/home/lth/lar...arithmetic.html
 
>
> I'd also seen this from the 2003 work.
> 
>
> Nolo contendre. But I am looking at performing some experiments with
> novel representations of inexact numbers and I thought that a GMP-
> based numerical tower would be easy for performing side-by-side
> comparisons. Obviously, having a Scheme implementation substrate that
> is relatively simple to work with is another important dimension to
> this choice.

Ikarus would probably be a good choice then.

--
Jens Axel Søgaard

On 27 mar, 14:37, Jens Axel Soegaard <inva...@soegaard.net> wrote:
> David Rush wrote: 
>
> I believe a number of Scheme implementations use GMP.
> On top of my head without any fact checking:
>
>    Chicken Scheme
>    Gambit
>    Guile
>    Ikarus
>    Larceny
>    PLT Scheme
>
> But using GMP is not always a good idea. Quoting
> AUbrey Jaffer:
>
> Numerical naivete apparently motivated developers of Guile, which is
> descended from SCM, to replace SCM's integrated arithmetics with an
> external package. Guile uses GNU MP:
>
>      I deleted all code belonging to the old bignum implementation and
>      replaced it with calls to some older GMP...
>
>      On my PII 266 with 64MB it now computes (factorial 10000) in about
>      two seconds, if no garbage collection occurs. If gc is activated
>      however, guile performs the calculation within 200KB and calls gc
>      several times. The whole thing takes about 25 seconds (!), but this
>      is still twice as fast as the old implementetation. (I do not
>      garantee for these figures).
>
> (factorial 10000) is a 118459.bit number. Numbers that large are of
> number-theoretical interest only. For example, secure encryption keys
> are currently 1024 bits. Public keys 100 times wider would take 10000
> times longer to compute; not practical for Internet shopping.
>
> That such a large number was necessary for FFT multiplication to prevail
> over O(b2) multiplication is high praise for the SCM implementation.
>
> Reference:
>
> http://swiss.csail.mit.edu/~jaffer/CNS/DIMPA.html
>
> --
> Jens Axel S=F8gaard

Hi, Axel.
I know for sure that Bigloo (the new alpha version) uses GMP. The
implementation is the work of Prof. J. Romildo, who worked in close
connection with Manuel Serrano. However, Serrano has an attitude that
I think that is not very good for the popularity of Bigloo. He insists
in not including third party libraries in his distribution. Therefore,
Bigloo checks your system; if it does not find GMP (or thread, or
Java, or dotNet), it does not install the features that require the
library. My group prepared a binary distribution for Windows, where we
have build Bigloo with the gmp library. You can get it at the
following address: code.google.com/stalingui

Prof. Romildo has written  a small but nice CAS in Bigloo (name iCAS)
to demonstrate the use of GMP. His bindings to GMP are very good,
since he analyzed the problems with garbage collectors (it seems that
Bigloo has conservative gc, and GMP has non conservative, or the other
way around), and solved them. He also eliminated the layer between
GMP, and the compiler, what makes his implementation soar.

On Mar 27, 5:26=A0pm, Scott <xsco...@gmail.com> wrote:

> Using a floating point FFT to implement integer multiplication is
> sketchy.

Error bounds that are good enough to multiply half-billion bit numbers
using floating-point fft were given by Colin Percival around 2002.
Gambit uses FFT multiplication with floating-point arithmetic, written
in Scheme.  For multiplication, division, and square roots of numbers
of about a million bits it's about half as fast as GMP, which is
written in C and assembler.

Brad

On Mar 27, 8:48 pm, Brad Lucier <luc...@math.purdue.edu> wrote:
> On Mar 27, 5:26 pm, Scott <xsco...@gmail.com> wrote:
> 
>
> Error bounds that are good enough to multiply half-billion bit numbers
> using floating-point fft were given by Colin Percival around 2002.
> Gambit uses FFT multiplication with floating-point arithmetic, written
> in Scheme.  For multiplication, division, and square roots of numbers
> of about a million bits it's about half as fast as GMP, which is
> written in C and assembler.
>
> Brad

I'm not saying you can't get it right.  All I claim is that a naive
implementation by someone using an FFT to get fast convolution while
ignoring the details that FFTs have noise from floating point error
can get you an algorithm that is wrong occasionally.  Different FFT
implementations have different amounts of noise based on their
twiddling schemes and such.  Faster FFTs might use a rougher twiddle
approximation, and "Occasionally wrong" is tough to track down.  With
Karatsuba's algorithm, all of the sub-products are precise, and O(n ^
log 3) with a small constant multiplier wins over O(n log n) for quite
a while until n gets pretty large.