darrell@jupiter.ucsc.edu (Darrell Long) (02/05/89)
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. If you have a good reference, or perhaps source code (C prefered), I will be grateful if you will send it to me. Thanks, DL
gwyn@smoke.BRL.MIL (Doug Gwyn ) (02/05/89)
In article <6235@saturn.ucsc.edu> darrell@jupiter.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.
So what's wrong with the ones in Knuth?andyb@coat.uucp (Andy Behrens) (02/06/89)
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)
--
Live justly, love gently, walk humbly.
Andy Behrens
andyb@coat.uucp
internet: andyb%coat@dartmouth.edu
uucp: {harvard,decvax}!dartvax!coat!andyb
Burlington Coat, PO Box 729, Lebanon, N.H. 03766 (603) 448-5000
piet@ruuinf (Piet van Oostrum) (02/06/89)
In article <6235@saturn.ucsc.edu>, darrell@jupiter (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.
`
`If you have a good reference, or perhaps source code (C prefered), I will be
`grateful if you will send it to me.
`
For source, you can look into MIT C-scheme, or GNU g++ lib, if you obey the
copyright (-left) conditions.
--
Piet van Oostrum, Dept of Computer Science, University of Utrecht
Padualaan 14, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands
Telephone: +31-30-531806. piet@cs.ruu.nl (mcvax!hp4nl!ruuinf!piet)cik@l.cc.purdue.edu (Herman Rubin) (02/08/89)
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)
mike@arizona.edu (Mike Coffin) (02/08/89)
From article <1122@l.cc.purdue.edu>, by cik@l.cc.purdue.edu (Herman Rubin): > 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. This is true. I once implemented arbitrary precision mulitplication using FFTs. I took reasonable care with the code, although I didn't do it in assembly language. When compared with the school-boy technique, it didn't break even until the factors were on the order of tens of thousands of bits. -- Mike Coffin mike@arizona.edu Univ. of Ariz. Dept. of Comp. Sci. {allegra,cmcl2}!arizona!mike Tucson, AZ 85721 (602)621-2858
bdb@becker.UUCP (Bruce Becker) (02/08/89)
In article <12099@dartvax.Dartmouth.EDU> andyb%coat@dartmouth.edu writes: +----------------- | In article <6235@saturn.ucsc.edu> Darrell Long writes: | [...] | | Donald Knuth | The Art of Computer Programming | Volume 2: Seminumerical Algorithms | (Addison-Wesley Publishing) | +----------------- Would anyone have a used copy of this book for sale? Thanks,