Xref: utzoo sci.crypt:1571 comp.sources.wanted:6267 sci.math.symbolic:578
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!purdue!mentor.cc.purdue.edu!l.cc.purdue.edu!cik
From: cik@l.cc.purdue.edu (Herman Rubin)
Newsgroups: sci.crypt,comp.sources.wanted,sci.math.symbolic
Subject: Re: Arbitrary precision integer arithmetic (reference sought)
Summary: Good coding is as important as a good algorithm
Keywords: arithmetic
Message-ID: <1122@l.cc.purdue.edu>
Date: 7 Feb 89 17:20:43 GMT
References: <6235@saturn.ucsc.edu> <9599@smoke.BRL.MIL> <12099@dartvax.Dartmouth.EDU>
Organization: Purdue University Statistics Department
Lines: 29

In article <12099@dartvax.Dartmouth.EDU>, andyb@coat.uucp (Andy Behrens) writes:
> 
>  In article <6235@saturn.ucsc.edu> Darrell Long writes:
> -I'm looking for a good reference on algorithms for arbitrary precision integer
> -arithmetic.  I need to do it fast, so naive (elementary school) algorithms
> -won't quite do it.
> 
> I'll second Doug Gwyn's recommendation.  Knuth's book will teach you
> as much about computer arithmetic as you are ever likely to need. The
> book in question is:
< 
< 	Donald Knuth
< 	The Art of Computer Programming
< 	Volume 2: Seminumerical Algorithms
< 	(Addison-Wesley Publishing)

Unless you have really long numbers, you are not likely to gain too much
from the fancy algorithms.  I also do not believe that Knuth has the
asymptotically fastest known algorithms using the discrete FFT over
finite rings.

But you are likely to gain a great deal by using the machine instructions
unavailable when using any of the HLLs.  This is the case whether or not
a fancy algorithm is used, and is probably more important if the FFT or
Toom-Cook or other non-elementary algorithm is used.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (Internet, bitnet, UUCP)