GMP integration
David Rush
integrating with the GMP libraries. Does anyone know what the current
state of play is on that topic?
david
Ludovic Courtès
David Rush <kumo...@gmail.com> writes:
GNU Guile 1.8 implements the full R5RS numeric tower using GMP.
Thanks,
Ludovic.
Abdulaziz Ghuloum
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.
Jens Axel Soegaard
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
Scott
>
> 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...
David Rush
> 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
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
Jens Axel Soegaard
> On Mar 27, 5:37 pm, Jens Axel Soegaard <inva...@soegaard.net> wrote:
>> 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
>
> I had no idea. I will definitely take a look.
>
>> Gambit
>
> I'm pretty sure this is false.
Indeed. (I think an old Gambit vs GMP benchmark confused me).
>> 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".
Did you try to fetch the lightweight repository?
The full repository takes *ages* to fetch.
>> Larceny
>
> 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/larceny/notes/note3-arithmetic.html
>> 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.
Ikarus would probably be a good choice then.
--
Jens Axel Søgaard
phi5...@yahoo.ca
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.
Brad Lucier
> 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
Scott
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.
Jens Axel Soegaard
> On Mar 27, 8:48 pm, Brad Lucier <luc...@math.purdue.edu> wrote:
>> On Mar 27, 5:26 pm, 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.
> 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.
I have faith in Lucier. He is everything but naive when it
comes to floating points.
"You're an evil man."
Linus Thorvalds on Lucier
The comment followed
http://gcc.gnu.org/ml/gcc-patches/2001-03/msg00463.html
which indeed is evil.
--
Jens Axel Søgaard
Jens Axel Soegaard
Impressive!
--
Jens Axel Søgaard
Scott
>
> I have faith in Lucier. He is everything but naive when it
> comes to floating points.
>
Yup, looks like I was teaching Gramma how to suck eggs on that
one... :-)
William D Clinger
> If the 1998 note still is correct, then Larceny has its own
> bignum implementation.
>
> http://www.ccs.neu.edu/home/lth/larceny/notes/note3-arithmetic.html
Right. Larceny does not use GMP.
Reliance on GMP would create portability problems, especially
for Common Larceny. There wouldn't be anything wrong with
changing native or Petit Larceny so they could use GMP on
machines for which GMP has been installed, but I spent
a couple of days looking into that and found that Larceny's
bignums have other performance problems that would have to
be fixed first. Once they're fixed, it looks like an
implementation of the Karatsuba algorithm in Scheme (which
I've already prototyped) would probably perform well enough
for most applications. We'd like to continue to distribute
ready-to-run binaries that don't depend on GMP, even if we
develop a version that can use GMP.
Will
Jens Axel Soegaard
That makes a lot of sense. Thanks for the explanation.
--
Jens Axel Søgaard
Abdulaziz Ghuloum
> We'd like to continue to distribute
> ready-to-run binaries that don't depend on GMP, even if we
> develop a version that can use GMP.
Wasn't there like a -static something flag for gcc that kind of
intended to solve that problem? (I haven't used it myself)
William D Clinger
> Wasn't there like a -static something flag for gcc that kind of
> intended to solve that problem? (I haven't used it myself)
It's more of a licensing issue than a technical issue.
Some of Larceny's binary distributions are unencumbered
by LGPL, and that matters to some users.
Will
Ludovic Courtès
William D Clinger <cesu...@yahoo.com> writes:
> It's more of a licensing issue than a technical issue.
> Some of Larceny's binary distributions are unencumbered
> by LGPL, and that matters to some users.
What do you mean by "unencumbered by LGPL"? LGPL is *not* copyleft.
Thanks,
Ludovic.
William D Clinger
> What do you mean by "unencumbered by LGPL"?
Read http://www.gnu.org/licenses/lgpl.html
> LGPL is *not* copyleft.
Understood. No part of Larceny is encumbered by GPL.
Only one part is even encumbered by LGPL. Two of the
binary distributions are encumbered by LGPL. The
others aren't. If this matters to you, which seems
unlikely considering your unfamiliarity with LGPL,
then you should read the COPYRIGHT file.
Will
Abdulaziz Ghuloum
You don't have to be encumbered by copyleft. My brain can be
enough encumbrance at times. :-)
Anyways, in a previous message, Will Clinger stated that:
"Petit Larceny is not encumbered by GPL
or LGPL or BSD or Apache licenses."
Given the number of licenses and people in the COPYRIGHT file
that comes with the larceny distribution (501 lines), it makes
me wonder what the implications of these licenses are. But as
per Will's comments, I'm sure had thought it all out.
Aziz,,,
William D Clinger
> Given the number of licenses and people in the COPYRIGHT file
> that comes with the larceny distribution (501 lines), it makes
> me wonder what the implications of these licenses are. But as
> per Will's comments, I'm sure had thought it all out.
The COPYRIGHT file reassures users of Larceny that all
code used in Larceny is used by permission of the copyright
holders. Those copyright holders have the right to attach
conditions and disclaimers, such as those listed in the
standard SRFI copyright notice. One of the more common
conditions, which is imposed by the SRFI copyright notice
among others, is that the full text of the owner's special
copyright notice must accompany the software. Larceny's
COPYRIGHT file discharges that legal obligation, even for
binary distributions.
The only copyright notice or license in the COPYRIGHT file
that imposes a burden substantially beyond that of the
standard SRFI copyright is the LGPL. See section 6d if you
are unfamiliar with its details.
I am aware that the LGPL imposes much less of a burden than
the GPL. No part of Larceny is encumbered by the GPL.
Several distributions of Larceny are not even encumbered by
the LGPL.
Will
Ludovic Courtès
William D Clinger <cesu...@yahoo.com> writes:
> Ludovic Courtès wrote:
>> What do you mean by "unencumbered by LGPL"?
>
> Read http://www.gnu.org/licenses/lgpl.html
Thank-you-very-much but can you please answer my question: what do you
mean by "unencumbered"?
I would understand in the case of GPL since it's copyleft, but I
honestly don't understand what you have in mind with LGPL.
Thanks,
Ludovic.
Jussi Piitulainen
> William D Clinger writes:
>> Ludovic Courtès wrote:
>>> What do you mean by "unencumbered by LGPL"?
>>
>> Read http://www.gnu.org/licenses/lgpl.html
>
> Thank-you-very-much but can you please answer my question: what do
> you mean by "unencumbered"?
>
> I would understand in the case of GPL since it's copyleft, but I
> honestly don't understand what you have in mind with LGPL.
Doesn't LGPL require you to provide the sources of the LGPL'd code to
those who get the binaries from you? And to allow the recipient to
rebuild the program using a possibly modified copy of that code? I
think it does.
I suppose someone wishes to distribute binary copies of some version
of Larceny without that hassle and the primary perpetrators of Larceny
want to allow that.
William D Clinger
> Ludovic Court�s writes:
> > William D Clinger writes:
Jussi's answer is entirely correct.
Will
Ludovic Courtès
Jussi Piitulainen <jpii...@ling.helsinki.fi> writes:
> Doesn't LGPL require you to provide the sources of the LGPL'd code to
> those who get the binaries from you?
Yes (if requested to do so).
I would not consider it an encumbrance since GMP is available on-line
anyway.
> And to allow the recipient to rebuild the program using a possibly
> modified copy of that code?
No.
For example, the GNU C Library is released under the LGPL v2 or later.
There are many proprietary programs linked against it, but obviously,
their vendors do not have to allow users to rebuild their programs.
Now I see that GMP is released under the LGPL v3 or later starting from
4.2.2 [0]. The potential problem it introduces is that it can no longer
be used by GPLv2-only programs [1].
Thanks,
Ludovic.
[0] http://gmplib.org/list-archives/gmp-announce/2007-September/000018.html
[1] http://gplv3.fsf.org/dd3-faq
Jussi Piitulainen
> Jussi Piitulainen writes:
>
>> Doesn't LGPL require you to provide the sources of the LGPL'd code
>> to those who get the binaries from you?
>
> Yes (if requested to do so).
>> And to allow the recipient to rebuild the program using a possibly
>> modified copy of that code?
>
> No.
Section 4 of LGPLv3, section 6 of LGPLv2.1, seem to say so.