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
很久没有分享PhotonVPS的消息,最近看到商家VPS主机套餐有一些更新所以分享下。这是一家成立于2008年的国外VPS服务商,Psychz机房旗下的站点,主要提供VPS和独立服务器等,数据中心包括美国洛杉矶、达拉斯、芝加哥、阿什本等。目前,商家针对Cloud VPS提供8折优惠码,优惠后最低2G内存套餐每月4美元起。下面列出几款主机配置信息。CPU:1core内存:2GB硬盘:30GB NVm...
香港最便宜的vps要多少钱?最便宜的香港vps能用吗?香港vps无需备案,整体性能好,而且租用价格便宜,使用灵活,因为备受站长喜爱。无论是个人还是企业建站,都比较倾向于选择香港VPS。最便宜的香港vps能用吗?正因为有着诸多租用优势,香港VPS在业内颇受欢迎,租用需求量也在日益攀升。那么,对于新手用户来说,香港最便宜的vps租用有四大要点是务必要注意的,还有易探云香港vps租用最便宜的月付仅18元...
Contabo自4月份在新加坡增设数据中心以后,这才短短的过去不到3个月,现在同时新增了美国纽约和西雅图数据中心。可见Contabo加速了全球布局,目前可选的数据中心包括:德国本土、美国东部(纽约)、美国西部(西雅图)、美国中部(圣路易斯)和亚洲的新加坡数据中心。为了庆祝美国独立日和新增数据中心,自7月4日开始,购买美国地区的VPS、VDS和独立服务器均免设置费。Contabo是德国的老牌服务商,...
212hhcom为你推荐
ip购买不同的ID不同的IP买同一个店铺同样的商品属于虚假交易吗?陈嘉垣陈浩民、马德钟强吻女星陈嘉桓,求大家一个说法。曲妙玲张婉悠香艳版《白蛇传》是电影还是写真集?同ip网站同IP的两个网站,做单向链接,会不会被K掉??seo优化工具SEO优化工具哪个好用点啊?seo优化工具seo优化软件有哪些?www.kaspersky.com.cn现在网上又有病毒了?www.ca800.com西门子plc仿真软件有什么功能dadi.tv智能网络电视smartTV是什么牌子5566.com请问如何创建网页(就是www.5566.com.cn这种格式的)
西安电信测速 stablehost 国外私服 谷歌香港 账号泄露 gtt 支付宝扫码领红包 购买国外空间 双线机房 环聊 测试网速命令 大化网 tracker服务器 ftp是什么东西 装修瓦工招聘 次时代主机 免费免备案cdn 杭州主机托管 灵动:鬼影实录4 阿里通免费网络电话 更多