Re: Bignum and rational arithmetic

Many have asked for a summary of responses to my earlier request for
references on bignums and rationals. Here it is, with some embedded
comments and further questions:


Request:


I'm looking for references on runtime systems for bignum and rational
arithmetic. Also sources for existing systems and comments from those
with experience.


In the latter category, I've already looked at AKCL, PARI, MIT-Scheme, and
the C++ classes distributed with djgpp.


How about garbage collection issues? I've seen a variety of ideas --
explicit malloc()/free() with copying assign, reference counting, and also
general purpose gc, and stacks for simple expressions.


Has anyone seen architectures with hardware support for unlimited
precision numbers? How do bignum calculations map onto your favorite
parallel architecture?


---
>From rockwell@socrates.umd.edu Fri Apr 24 06:47:42 1992


      How about garbage collection issues?


You can also treat bignums as an array of numbers -- this is just like a
regular array, but the last dimension is devoted to the entire magnitude
of an individual number.


[ I'm mystified . The only internal rep I've seen is
    vector of 2^n digits (15 <= n <= 32). Does this have
    to do with garbage collection? GR ]


      How do bignum calculations map onto your favorite parallel architecture?
      Has anyone seen architectures with hardware support for unlimited
      precision?


Once you've got a semi-predictable size associated with your bignums (I'm
assuming a dynamic implementation of arrays), the rest falls out of the
implementation. Carry propagation requires communication for 1 or more
ops (till it settles). The summation used in multiplication requires a
sort of diagonalization of the result array (the intermediate result has
two dimensions devoted to representing an individual number).


[ Mystified again. At best size can be predicted only as a function
    of input sizes. How can propagated carries `settle'? How
    does shift and add relate to diagonalization? GR ]


      Finally, who are the big users of bignums and rationals? I'm aware
      of cryptography applications, also computational geometry. Others?


I dunno, I just treated them as a programming exercise.


  ---
>From mario@computer-science.manchester.ac.uk Fri Apr 24 08:38:20 1992


You might want to look at the LargePositiveInteger, LargeNegativeInteger
and Fraction classes in a Smalltalk system.


In Smalltalk, if a primitive arithmetic method on small integers (such as
multiplication) results in overflow or underflow, Smalltalk code can take
over, and perform the arithmetic using large integers (aka bignums).
Similarly, division between two integers results in a Fraction object.
All the large integer and fraction operations are usually implemented in
Smalltalk, so source is available in the system.


Large integers and fractions are garbage-collected using the general GC
mechanisms.


In a typical Smalltalk system the bignum capability is used realtively
infrequently (1% or so of all arithmetic operations). The book
"Smalltalk-80: Bits of History, Words of Advice" (ed Goldberg and Robson,
pub. Addison-Wesley, 1984) has statistics on usage patterns.


[ All these observations apply to the Lisps I've examined, too. GR ]


  ---
>From simon@liasun1.epfl.ch Fri Apr 24 05:20:53 1992


    I think you can get a paper about the implementation of BIGNUMs for
Portable Standard Lisp on CRAY computers from my former colleagues at the
following address:


Herbert Melenk
Konrad-Zuse-Zentrum fuer Informationstechnik
Abt. Symbolik
Heilbronner Strasse 10
1000 Berlin 15
Federal Republic of Germany


or maybe even by email to <melenk@symbolik.zib-berlin.de>.


While CRAY is not the best of all architectures for Lisp in general,
BIGNUM arithmetic can make good use of the vector facilities on these
machines.


  ---
>From sjs@cs.brown.edu Fri Apr 24 08:44:35 1992


> Finally, who are the big users of bignums and rationals? I'm aware of
> cryptography applications, also computational geometry. Others?


Most serious constraint logic programming languages offer rationals as one
of their basic computation domains.


[ Have only seen the work of Lassez in this area. Is this what we're
    talking about? GR ]


Sebastien.


  ---
>From paco@cs.rice.edu Fri Apr 24 11:14:49 1992


Boehm and Lee did some work here, and Boehm may have done some more after
moving to Xerox PARC.


One reference is


Optimizing Programs over the Constructive Reals
Vernon Lee & Hans Boehm
SIGPLAN '90 PLDI, White Plains, N.Y.
SIGPLAN Notices 25:6, June 1990; pages 102-111


--Paul
  ---
>From pardo@cs.washington.edu Fri Apr 24 11:42:28 1992


SunOS comes with an arbitrary-precision math package, I think it's called
`mp' or something. I can take a look if you don't have access to a
machine that has it.


[ `mp' is reputed to be slow and doesn't do rationals. GNU's version
      rectifies the latter problem and also the former to some extent. GR ]


Hans Boehm (@ Xerox PARC, formerly of Rice) has done extensive work in the
field of arbitrary precision calculation. He has a number of papers, [see
above.]


  ---
>From zycad!zycad.com!vernon@netcom.com Fri Apr 24 12:34:41 1992


Another reference (with a pretty good bibliography):


Optimizing Programs over the Constructive Reals, PhD Thesis, Rice
University, Vernon Lee, 1991.


You can get a fairly cheap copy of this by contacting the dept of computer
science and asking for the Tech Report. I'm sorry but I can't find the TR
number.


I'll be happy to answer any questions you might have...


Vernon Lee


---
>From xleroy@margaux.inria.fr Sat Apr 25 06:33:44 1992


You might find interesting the BIGNUM package developed at INRIA and DEC
PRL. It is described in:


                Bernard Serpette, Jean Vuillemin, Jean-Claude Herv\'e.
                BigNum: A Portable and Efficient Package for Arbitrary-Precision
                Arithmetic.
                Research report number 2, DEC Paris Research Laboratory, 1989.


Contact Bernard.Serpette@inria.fr for information on the package and how
to get it.


[ Reputed to be complete and fast. GR ]


>Finally, who are the big users of bignums and rationals? I'm aware of
>cryptography applications, also computational geometry. Others?


Computer algebra systems, like Maple or Macsyma.


[ But Macsyma is built over Lisp, no? GR ]


- Xavier Leroy


---
>From cwitty@ai.mit.edu Sat Apr 25 21:03:46 1992


For another example of a system using bignums and rationals, you could
look at Calc, a full-featured symbolic calculator written in GNU Emacs
Lisp. Among other things, it uses bignums for the mantissas of
arbitrary-precision floating-point numbers.


Calc is available by anonymous ftp from csvax.cs.caltech.edu and
prep.ai.mit.edu.


Carl Witty
cwitty@ai.mit.edu


---
>From pmontgom@math.ucla.edu Sat Apr 25 21:33:55 1992


Most of my experience is with a Fortran system where maximum sizes
must be declared at compiler time. For my application (integer
factorization via elliptic curve and related methods) most operations are
modular arithmetic (e.g. A = B - C mod N), where 100000 operations are
done before N changes. The sizes of A, B, C are that of N, perhaps with
leading zeros.


[ Is this a common extension to FORTRAN? GR ]


>How do bignum calculations map onto your favorite parallel architecture?


I have used only an Alliant. The Alliant is both vectorized and
parallel. But there is no vectorized double length integer product
instruction. I had to switch to floating point algorithms. Even then,
the typical vector lengths (e.g., 17 for 150-digit numbers expressed in
radix 2^30) were small.


My modular multiplication algorithm (see Mathematics of
Computation, April, 1985) seems well-suited for a SIMD architecture, if
all moduli are equal sizes (and doing a separate modular multiplication on
each processor). But I haven't had an opportunity to try it there,


>Finally, who are the big users of bignums and rationals? I'm aware of
>cryptography applications, also computational geometry. Others?


I am in computational number theory, a cousin of cryptography.


I will soon be joining a project which will do enormous
calculations over algebraic number fields (say degree 5). We anticipate
needing to take


SQRT(n1 * n2 * ... * n100000)


where each ni may have 6-digit integer coefficients (we anticipate the
product is a perfect square). That is, we may need


SQRT(a0 + a1*alpha + a2*alpha^2 +a3*alpha^3 + a4*alpha^4)


where each ai has 600000 digits and alpha satisfies an irreducible
polynomial of degree 5. One plan is to find a prime p such that alpha's
polynomial is irreducible mod p, take the p-adic square root (which will
be unique up to sign), and use this to get the original square root.
Variations will use a combination of multiplication and division, such as


                                                                              n50001 * ... * n100000
n1 * n2 *... * n50000 * SQRT (----------------------- ),
                                                                              n1 * n2 * ... * n50000


in an attempt to reduce the coefficients of the operand to SQRT.


Polynomial factorization over Z (integers) often works over these
p-adic rings, using bounds on the coefficients of potential factors.


Scientific users solve big systems of equations. Knuth, in one of
his three volumes, reports a case where an unstable system was solved
modulo several primes to get a rational solution in less time than the
floating point algorithms could get an approximate solution.


In one paper I am preparing, we need to test whether some real
numbers are linearly dependent. We may compute each to 100 decimal
places, then generate the integer vectors


(round(x1*10^100), 1, 0, 0)
(round(x2*10^100), 0, 1, 0)
(round(x3*10^100), 0, 0, 1)


Now we try to find the shortest vector in the lattice generated by these
three vectors over Z. If that vector is (a, b, c, d) where a, b, c, d are
small (say <= 10^10), then we conjecture that b*x1 + c*x2 + d*x3 = 0.


[ Neat. Does anyone use Schoenhagen-Strassen on these huge problems? GR ]


---
Reply-To: Julian Seward (DRL PhD) <sewardj@computer-science.manchester.ac.uk>


David Lester (dlester@uk.ac.man.cs) has interests in


      - bignum arithmetic
      - cryptography
      - parallel functional language implementations


Perhaps you should contact him.


J.


---
Reply-To: neil@bedford.progress.COM (Neil Galarneau)


The public domain programming language icon has bignums.


I believe they are mentioned in the book on the design of icon.


Neil
neil@progress.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.