Moby ints [Re: Num Rat]

> pjm@ionia.engr.sgi.com (Patrick May) writes:
> This invocation of the name of the diety reminds me of a question
> I've been meaning to ask.  Is Knuth still a good source of algorithms
> for implementing large integers or do more recent books exist that
> contain superior methods?

While Knuth is now and forever the algorithm deity in general, Arjen
Lenstra is as close to godhood as one can get in moby ints these days.

I'd look at the Lip package Lenstra wrote; it's used in his state of the
art factoring programs.  It's available with masses of PostScript
documentation from ftp.ox.ac.uk.  Studying the code and docs might remind
you of some issues that aren't obvious... and, of course, you might decide
you don't need to write a moby int package, but could just use his library.

	Jim Gillogly
	Hevensday, 18 Afterlithe S.R. 1995, 18:48

The state of the art in multiprecision integer arithmetic is Scho"nhage.
Schonhage invented the all-integer Fast-Fourier-Transform based 
big-int multiplication method. An n-bit can be multiplied in O(n ln n) 
operations. This is a big improvement over the Karatsuba method which is
O(n^1.5) and the classical method O(n^2). Surprisingly, the constant
factor isn't that large. This can be combined with modmult techniques
for fast modexp routines. However, it's only worthwhile for large
numbers (>512 bits). At n=512, if your bigints are stored as polynomials
with a 32-bit radix, then N=512/32=16. 16^1.5 = 64, 16 * lg(16) = 64
(so the FFT method and the Karatsuba method are equivalent for numbers
of that size)

If you are dealing with 2048 or 4096 bit keys, it starts to look attractive.


Schonhage published a book in the last year, the result of more than 10 
years of research into this area. It's hard to get a hold of though, you
have to order it from germany.

95-133299: Schonhage, Arnold.  Fast algorithms : a multitape Turing
     machine implementation /  Mannheim : B.I. Wissenschaftsverlag, 
     c1994.  x,
     297 p. : ill. ; 25 cm.