h0212hhcom

Algorithmicnumbertheory,editedbyBuhlerandStevenhagen,toappear.
FASTMULTIPLICATIONANDITSAPPLICATIONSDANIELJ.
BERNSTEINAbstract.
Thissurveyexplainshowsomeusefularithmeticoperationscanbespedupfromquadratictimetoessentiallylineartime.
§2.
Product:theFFTcase§13.
Sumoffractions§3.
Product:extension§11.
Matrixproduct§14.
Fractionfromcontinuedfraction§4.
Product:zero-paddingandlocalization55kkkkkkkkkkkkk§12.
Producttree::uuuuuuuuuuuuuuuuuuuuuuuuuu$$IIIIIIIIIIIIIIIIIIIIIIIIII55jjjjjjjjjjjjjjjj§20.
Smallfactorsofasequence§5.
Product:completion§15.
Exponential:theshortcase§19.
SmallfactorsofaproductOO§6.
Reciprocal§16.
Exponential:thegeneralcase§18.
RemaindertreeOO§7.
Quotient//§17.
Quotientandremainder55jjjjjjjjjjjjjjjj§23.
Interpolator§8.
Logarithm:theseriescase§21.
Continuedfractionfromfraction//§22.
GreatestcommondivisorOO§9.
Exponential:theseriescase//§10.
Power:theseriescase§24.
CoprimebaseFigure1.
Outlineofthepaper.
Avertex"§N.
F"heremeansthatSectionNdescribesanalgorithmtocomputethefunctionF.
Arrowshereindicateprerequisitealgorithms.
Date:2004.
10.
07.
PermanentIDofthisdocument:8758803e61822d485d54251b27b1a20d.
2000MathematicsSubjectClassication.
Primary68–02.
Secondary11Y16,12Y05,65D20,65T50,65Y20,68W30.
12DANIELJ.
BERNSTEIN1.
IntroductionThispaperpresentsfastalgorithmsforseveralusefularithmeticoperationsonpolynomials,powerseries,integers,realnumbers,and2-adicnumbers.
Eachsectionfocusesononealgorithmforoneoperation,anddescribessevenfeaturesofthealgorithm:Input:WhatnumbersareprovidedtothealgorithmSections2,3,4,and5explainhowvariousmathematicalobjectsarerepresentedasinputs.
Output:WhatnumbersarecomputedbythealgorithmSpeed:HowmanycoecientoperationsdoesthealgorithmusetoperformapolynomialoperationTheanswerisatmostn1+o(1),wherenistheproblemsize;eachsectionstatesamorepreciseupperbound,oftenusingthefunctiondenedinSection4.
Howitworks:WhatisthealgorithmThealgorithmmayusepreviousalgorithmsassubroutines,asshownin(thetransitiveclosureof)Figure1.
Theintegercase(exceptinSection2):Theinputswerepolynomials(orpowerseries);whatabouttheanalogousoperationsonintegers(orrealnumbers)WhatdicultiesariseinadaptingthealgorithmtointegersHowmuchtimedoestheadaptedalgorithmtakeHistory:HowweretheseideasdevelopedImprovements:Thealgorithmwaschosentobereasonablysimple(subjecttothen1+o(1)bound)attheexpenseofspeed;howcanthesamefunctionbecomputedevenmorequicklySections2through5describefastmultiplicationalgorithmsforvariousrings.
Theremainingsectionsdescribevariousapplicationsoffastmultiplication.
Hereisasimpliedsummaryofthefunctionsbeingcomputed:§6.
Reciprocal.
f→1/fapproximation.
§7.
Quotient.
f,h→h/fapproximation.
§8.
Logarithm.
f→logfapproximation.
§9.
Exponential.
f→expfapproximation.
Also§15,§16.
§10.
Power.
f,e→feapproximation.
§11.
Matrixproduct.
f,g→fgfor2*2matrices.
§12.
Producttree.
f1,f2,f3,treeofproductsincludingf1f2f3···.
§13.
Sumoffractions.
f1,g1,f2,g2,f1/g1+f2/g2§14.
Fractionfromcontinuedfraction.
q1,q2,q1+1/(q2+1/§17.
Quotientandremainder.
f,h→h/f,hmodf.
§18.
Remaindertree.
h,f1,f2,hmodf1,hmodf2,§19.
Smallfactorsofaproduct.
S,h1,h2,S(h1h2···)whereSisasetofprimesandS(h)isthesubsetofSdividingh.
§20.
Smallfactorsofasequence.
S,h1,h2,S(h1),S(h2)§21.
Continuedfractionfromfraction.
f1,f2→q1,q2,.
.
.
withf1/f2=q1+1/(q2+1/§22.
Greatestcommondivisor.
f1,f2→gcd{f1,f2}.
§23.
Interpolator.
f1,g1,f2,g2,hwithh≡fj(modgj).
§24.
Coprimebase.
f1,f2,coprimesetSwithf1,f2,S.
Acknowledgments.
ThankstoAliceSilverberg,PaulZimmermann,andtheref-ereefortheircomments.
FASTMULTIPLICATIONANDITSAPPLICATIONS32.
Product:theFFTcaseInput.
Letn≥1beapowerof2.
LetcbeanonzeroelementofC.
Thealgorithmdescribedinthissectionisgiventwoelementsf,goftheringC[x]/(xnc).
AnelementofC[x]/(xnc)is,byconvention,representedasasequenceofnelementsofC:thesequence(f0,f1,fn1)representsf0+f1x+···+fn1xn1.
Output.
Thisalgorithmcomputestheproductfg∈C[x]/(xnc),representedinthesameway.
Iftheinputisf0,f1,fn1,g0,g1,gn1thentheoutputish0,h1,hn1,wherehi=0≤j≤ifjgij+ci+1≤jd.
Reversethecoecientorderinf=jfjxjtoobtainF=jfdjxj∈A[x];inotherwords,deneF=xdf(x1).
ThendegF≤dandF(0)=1.
Forexample,ifd=2andf=f0+f1x+x2,thenF=1+f1x+f0x2.
Similarly,reverseh=jhjxjtoobtainH=jhe1jxj∈A[x];inotherwords,deneH=xe1h(x1).
ThendegHdegg2;ifalsoM21=0thendegg1=degf2degM21.
(Proof:degM12g2degg2,andM22f2=g2M21f1,sodegM22f2=degM21f1.
)Speed.
ThisalgorithmusesO(d(lgd)2lglgd)operationsinA.
Moreprecisely:Assumethat2d≤2kwherekisanonnegativeinteger.
Thenthisalgorithmusesatmost(46dk+44(2k+11))((4d+8)+1)operationsinA.
Thisboundispessimistic.
Howitworks.
ThedesiredmatrixMiscomputedinninestepsshownbelow.
ThedesiredfactorizationofMisvisiblefromtheconstructionofM,asisthe(consequent)factthatdetM∈{1,1}.
Thereareseveralrecursivecallsinthisalgorithm.
Mostoftherecursivecallsreduced;theotherrecursivecallspreservedandreducedegf2.
Thetimeanalysisinductson(d,degf2)inlexicographicorder.
Step1:xtheinputorder.
Ifdegf10:Applythealgorithmrecursivelytod,f1/xi,f2/xitondamatrixM,ofdegreeatmostd,suchthatdeg(M21f1/xi+M22f2/xi)2.
0.
CO;2-Y.
[82]HendrikW.
Lenstra,Jr.
,RobertTijdeman(editors),ComputationalmethodsinnumbertheoryI,MathematicalCentreTracts,154,MathematischCentrum,Amsterdam,1982.
ISBN90–6196–248–X.
MR84c:10002.
[83]Jean-BernardMartens,Recursivecyclotomicfactorization—anewalgorithmforcalculatingthediscreteFouriertransform,IEEETransactionsonAcoustics,Speech,andSignalPro-cessing32(1984),750–761.
ISSN0096–3518.
MR86b:94004.
URL:http://cr.
yp.
to/bib/entries.
html#1984/martens.
[84]RobertT.
Moenck,FastcomputationofGCDs,in[6](1973),142–151.
URL:http://cr.
yp.
to/bib/entries.
html#1973/moenck.
46DANIELJ.
BERNSTEIN[85]RobertT.
Moenck,AllanBorodin,Fastmodulartransformsviadivision,in[67](1972),90–96;newerversion,notasuperset,in[20].
URL:http://cr.
yp.
to/bib/entries.
html#1972/moenck.
[86]PeterL.
Montgomery,Modularmultiplicationwithouttrialdivision,MathematicsofCom-putation44(1985),519–521.
ISSN0025–5718.
MR86e:11121.
[87]PeterL.
Montgomery,AnFFTextensionoftheellipticcurvemethodoffactorization,Ph.
D.
thesis,UniversityofCaliforniaatLosAngeles,1992.
[88]PeterJ.
Nicholson,AlgebraictheoryofniteFouriertransforms,JournalofComputerandSystemSciences5(1971),524–547.
ISSN0022–0000.
MR44:4112.
[89]HenriJ.
Nussbaumer,Fastpolynomialtransformalgorithmsfordigitalconvolution,IEEETransactionsonAcoustics,Speech,andSignalProcessing28(1980),205–215.
ISSN0096–3518.
MR80m:94004.
URL:http://cr.
yp.
to/bib/entries.
html#1980/nussbaumer.
[90]ChristosM.
Papadimitriou,Computationalcomplexity,Addison-Wesley,Reading,Mas-sachusetts,1994.
ISBN0201530821.
MR95f:68082.
[91]NicolasPapamichael,StephanRuscheweyh,EdwardB.
Sa(editors),Computationalmeth-odsandfunctiontheory1997:proceedingsofthethirdCMFTconference,13–17October1997,Nicosia,Cyprus,SeriesinApproximationsandDecompositions,11,WorldScientic,Singapore,1999.
ISBN9810236263.
MR2000c:00029.
[92]JohnM.
Pollard,ThefastFouriertransforminaniteeld,MathematicsofComputation25(1971),365–374.
ISSN0025–5718.
MR46:1120.
URL:http://cr.
yp.
to/bib/entries.
html#1971/pollard.
[93]ArnoldL.
Rosenberg(chairman),FourthannualACMsymposiumontheoryofcomputing,AssociationforComputingMachinery,NewYork,1972.
MR50:1553.
[94]EugeneSalamin,Computationofπusingarithmetic-geometricmean,MathematicsofCom-putation30(1976),565–570.
ISSN0025–5718.
MR53:7928.
[95]JosefSchicho(editor),Proceedingsofthe2004internationalsymposiumonsymbolicandalgebraiccomputation,AssociationforComputingMachinery,NewYork,2004.
ISBN1–58113–827–X.
[96]ArnoldSch¨onhage,MultiplikationgroerZahlen,Computing1(1966),182–196.
ISSN0010–485X.
MR34:8676.
URL:http://cr.
yp.
to/bib/entries.
html#1966/schoenhage.
[97]ArnoldSch¨onhage,SchnelleBerechnungvonKettenbruchentwicklugen,ActaInformat-ica1(1971),139–144.
ISSN0001–5903.
URL:http://cr.
yp.
to/bib/entries.
html#1971/schoenhage-gcd.
[98]ArnoldSch¨onhage,SchnelleMultiplikationvonPolynomen¨uberK¨orpernderCharakteristik2,ActaInformatica7(1977),395–398.
ISSN0001–5903.
MR55:9604.
URL:http://cr.
yp.
to/bib/entries.
html#1977/schoenhage.
[99]ArnoldSch¨onhage,Asymptoticallyfastalgorithmsforthenumericalmultiplicationanddi-visionofpolynomialswithcomplexcoecients,in[36](1982),3–15.
MR83m:68064.
URL:http://cr.
yp.
to/bib/entries.
html#1982/schoenhage.
[100]ArnoldSch¨onhage,Variationsoncomputingreciprocalsofpowerseries,InformationPro-cessingLetters74(2000),41–46.
ISSN0020–0190.
MR2001c:68069.
[101]ArnoldSch¨onhage,AndreasF.
W.
Grotefeld,EkkehartVetter,Fastalgorithms:amultitapeTuringmachineimplementation,BibliographischesInstitut,Mannheim,1994.
ISBN3–411–16891–9.
MR96c:68043.
[102]ArnoldSch¨onhage,VolkerStrassen,SchnelleMultiplikationgroerZahlen,Computing7(1971),281–292.
ISSN0010–485X.
MR45:1431.
URL:http://cr.
yp.
to/bib/entries.
html#1971/schoenhage-mult.
[103]ArnoldSch¨onhage,EkkehartVetter,Anewapproachtoresultantcomputationsandotheralgorithmswithexactdivision,in[120](1994),448–459.
MR96d:68109.
[104]MalteSieveking,Analgorithmfordivisionofpowerseries,Computing10(1972),153–156.
ISSN0010–485X.
MR47:1257.
URL:http://cr.
yp.
to/bib/entries.
html#1972/sieveking.
[105]ThomasSimpson,Essaysonseveralcuriousandusefulsubjectsinspeculativeandmix'dmathematics,illustratedbyavarietyofexamples,1740.
[106]JonathanSorenson,TwofastGCDalgorithms,JournalofAlgorithms16(1994),110–144.
ISSN0196–6774.
MR94k:11135.
[107]DamianStelhe,PaulZimmermann,Abinaryrecursivegcdalgorithm,in[32](2004),411–425.
FASTMULTIPLICATIONANDITSAPPLICATIONS47[108]ThomasG.
Stockham,Jr.
,High-speedconvolutionandcorrelation,in[2](1966),229–233.
URL:http://cr.
yp.
to/bib/entries.
html#1966/stockham.
[109]HaroldS.
Stone,Anecientparallelalgorithmforthesolutionofatridiagonallinearsystemofequations,JournaloftheACM20(1973),27–38.
ISSN0004–5411.
MR48:12792.
URL:http://cr.
yp.
to/bib/entries.
html#1973/stone.
[110]VolkerStrassen,Gaussianeliminationisnotoptimal,NumerischeMathematik13(1969),354–356.
ISSN0029–599X.
MR40:2223.
URL:http://cr.
yp.
to/bib/entries.
html#1969/strassen.
[111]VolkerStrassen,DieBerechnungskomplexit¨atvonelementarsymmetrischenFunktionenundvonInterpolationskoezienten,NumerischeMathematik20(1973),238–251.
ISSN0029–599X.
MR48:3296.
[112]VolkerStrassen,Thecomputationalcomplexityofcontinuedfractions,in[122](1981),51–67;seealsonewerversion[113].
URL:http://cr.
yp.
to/bib/entries.
html#1981/strassen.
[113]VolkerStrassen,Thecomputationalcomplexityofcontinuedfractions,SIAMJournalonComputing12(1983),1–27;seealsoolderversion[112].
ISSN0097–5397.
MR84b:12004.
URL:http://cr.
yp.
to/bib/entries.
html#1983/strassen.
[114]JamesJ.
Sylvester,Onafundamentalruleinthealgorithmofcontinuedfractions,Philo-sophicalMagazine6(1853),297–299.
URL:http://cr.
yp.
to/bib/entries.
html#1853/sylvester.
[115]AndreiL.
Toom,Thecomplexityofaschemeoffunctionalelementsrealizingthemultipli-cationofintegers,SovietMathematicsDoklady3(1963),714–716.
ISSN0197–6788.
[116]JosephF.
Traub,Analyticcomputationalcomplexity,AcademicPress,NewYork,1976.
MR52:15938.
[117]JohannesW.
M.
Turk,Fastarithmeticoperationsonnumbersandpolynomials,in[82](1982),43–54.
MR84f:10006.
URL:http://cr.
yp.
to/bib/entries.
html#1982/turk.
[118]JorisvanderHoeven,Fastevaluationofholonomicfunctions,TheoreticalComputerScience210(1999),199–215.
ISSN0304–3975.
MR99h:65046.
URL:http://www.
math.
u-psud.
fr/~vdhoeven/.
[119]JorisvanderHoeven,Fastevaluationofholonomicfunctionsnearandinregularsin-gularities,JournalofSymbolicComputation31(2001),717–743.
ISSN0747–7171.
MR2002j:30037.
URL:http://www.
math.
u-psud.
fr/~vdhoeven/.
[120]JanvanLeeuwen(editor),Algorithms—ESA'94,LectureNotesinComputerScience,855,Springer-Verlag,Berlin,1994.
ISBN3–540–58434–X.
MR96c:68002.
[121]MartinVetterli,HenriJ.
Nussbaumer,SimpleFFTandDCTalgorithmswithreducednum-berofoperations,SignalProcessing6(1984),262–278.
ISSN0165–1684.
MR85m:65128.
URL:http://cr.
yp.
to/bib/entries.
html#1984/vetterli.
[122]PaulS.
Wang(editor),SYM-SAC'81:proceedingsofthe1981ACMSymposiumonSym-bolicandAlgebraicComputation,Snowbird,Utah,August5–7,1981,AssociationforCom-putingMachinery,NewYork,1981.
ISBN0–89791–047–8.
[123]ArnoldWeinberger,J.
L.
Smith,Alogicforhigh-speedaddition,NationalBureauofStan-dardsCircular591(1958),3–12.
ISSN0096–9648.
[124]R.
Yavne,AneconomicalmethodforcalculatingthediscreteFouriertransform,in[4](1968),115–125.
URL:http://cr.
yp.
to/bib/entries.
html#1968/yavne.
[125]TjallingJ.
Ypma,HistoricaldevelopmentoftheNewton-Raphsonmethod,SIAMReview37(1995),531–551.
ISSN1095–7200.
MR97b:01003.
DepartmentofMathematics,Statistics,andComputerScience(M/C249),TheUni-versityofIllinoisatChicago,Chicago,IL60607–7045E-mailaddress:djb@cr.
yp.
to