[plt-scheme] Bignums in Scheme

Marco Morazan wrote:

> I am writing to inquire if you are aware of any articles/documents
> that describe how bignums (arbitrarily large integers) are implemented
> in Scheme. I am particularly interested in how bignums are represented
> and the algorithms used for bignum arithmetic. I am also looking for
> performance studies (speed and memory) that may exist. Both
> descriptions of native implementations and use of foreign libraries
> are of interest to me.

Quite a few Schemes use the GNU GMP library for bignum calculations.
The source of this isn't for the faint of heart though. One of the best
introductions to large number arithmetics and computer algebra
algorithms in general is "Modern Computer Algebra" by Joachim von
sur Gathen and Jürgen Gerhard. (<http://www-math.uni-paderborn.de/mca/>)

If you are more interested in Scheme implementations of the
central algorithms than actual production code the article

   Arbitrarily Large Bignums - Three easy substrates
   By André van Meulebrouck
   <http://www.mactech.com/articles/mactech/Vol.08/08.03/BigNums/>

might be of your taste.

That said, there are a few Schemes that have their own bignum
implementations. Among these is Larceny

   <http://www.ccs.neu.edu/home/lth/larceny/notes/note3-arithmetic.html>

where the bignum operations (AFAIK) is implemented in Scheme.

MIT Scheme and SCM also have their own bignum implementations.

Finally Lucier uses Feeley's Gambit for his computations, so
the source of Gambit might also be interesting (I can't
remember their implementation choice though)

As for descriptions of speed, the study by Jaffer

   The Distribution of Integer Magnitudes in Polynomial Arithmetic
   <http://swiss.csail.mit.edu/~jaffer/CNS/DIMPA>

shows that for "normal" calculations the standard Karatsuba
algorithm is enough.


Finally the classic algorithms are described in Knuth: The Art of
Computer Programming.

-- 
Jens Axel Søgaard