Xref: utzoo sci.crypt:1573 comp.sources.wanted:6268 sci.math.symbolic:579
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!bionet!ig!arizona!mike
From: mike@arizona.edu (Mike Coffin)
Newsgroups: sci.crypt,comp.sources.wanted,sci.math.symbolic
Subject: Re: Arbitrary precision integer arithmetic (reference sought)
Message-ID: <9079@megaron.arizona.edu>
Date: 7 Feb 89 19:24:36 GMT
References: <1122@l.cc.purdue.edu>
Organization: U of Arizona CS Dept, Tucson
Lines: 15

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