Article View: sci.crypt
Article #4298Re: Arbitrary precision integer arithmetic (reference sought)
From: Mike Coffin
Date: Tue, 07 Feb 1989 19:24
Date: Tue, 07 Feb 1989 19:24
15 lines
1183 bytes
1183 bytes
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
Technical Details
Message-ID:
<9079@megaron.arizona.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!bionet!ig!arizona!mikeReferences:
<1122@l.cc.purdue.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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