Wed, 29 Apr 1992 14:27:13 GMT

Related articles |
---|

Bignum and rational arithmetic ressler@cs.cornell.edu (1992-04-24) |

Re: Bignum and rational arithmetic ressler@cs.cornell.edu (1992-04-29) |

Newsgroups: | comp.programming,comp.compilers |

From: | ressler@cs.cornell.edu (Gene Ressler) |

Keywords: | arithmetic, summary |

Organization: | Cornell Univ. CS Dept, Ithaca NY 14853 |

References: | 92-04-121 |

Date: | Wed, 29 Apr 1992 14:27:13 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.