Harvey-van der Hoevens algoritm

Harvey-van der Hoeven-  algoritmen är en algoritm för att multiplicera två -bitars heltal med tidskomplexitet i multitape Turing-maskinmodellen . Föreslagit av matematikerna David Harvey från University of New South Wales och Joris van der Hoeven från French National Centre for Scientific Research . Från och med 2020 är det den snabbaste kända algoritmen för att multiplicera tal i denna modell, medan uppskattningen av tidskomplexiteten för multiplikationsalgoritmer verkar vara oförbättrad.

Historik

Frågan om förekomsten av snabba algoritmer för att multiplicera heltal upptar en viktig plats i teorin om beräkningskomplexitet . De mest välkända multiplikationsmetoderna, såsom staplad multiplikation, kräver aritmetiska operationer. Denna uppskattning förbättrades först 1960 av Anatoly Karatsuba , som föreslog en algoritm för multiplikation med körtid [1] . 1971 föreslog Schönhage och Strassen en algoritm baserad på den snabba Fouriertransformen över tid [2] . I samma arbete lägger de fram en hypotes att den optimala multiplikationsalgoritmen kräver elementära operationer. Under lång tid förblev dock den övre gränsen som ges av Schönhage och Strassen-algoritmen utan förbättring. Först 2007, 36 år senare, föreslog Martin Fuhrer en algoritm med körtid för en ospecificerad konstant , där  är en itererad logaritm [3] . Därefter förbättrade Harvey och van der Hoeven denna uppskattning först till [4] , och sedan till , vilket bekräftade den övre gränsen som lagts fram i antagandet om Schönhage och Strassen [5] . Algoritmen är av stor teoretisk betydelse, eftersom den uppnår en hypotetisk nedre gräns för körtiden för talmultiplikationsalgoritmer i Turing-maskinmodellen med flera band. Praktisk acceleration uppnås dock endast på tal vars binära längd överstiger en bit, medan antalet partiklar i det observerbara universum uppskattas till [6] .

Anteckningar

1. ↑ A. Karatsuba, Y. Offman. Multiplikation av flervärdiga tal på automater  // Dokl. USSR:s vetenskapsakademi. - 1962. - 9 februari ( vol. 145 , nr 2 ). - S. 293-294 .
2. ↑ A. Schönhage, V. Strassen. Schnelle Multiplikation großer Zahlen  (tyska)  // Computing. — 1971-09-01. — bd. 7 , H. 3 . — S. 281–292 . — ISSN 1436-5057 . - doi : 10.1007/BF02242355 .
3. ↑ Martin Furer. Snabbare heltalsmultiplikation  (engelska)  // SIAM Journal on Computing. — 2009-01. — Vol. 39 , iss. 3 . — S. 979–1005 . - ISSN 1095-7111 0097-5397, 1095-7111 . - doi : 10.1137/070711761 .
4. ↑ David Harvey, Joris van der Hoeven. Snabbare heltalsmultiplikation med korta gittervektorer  //  The Open Book Series. — 2019-01-28. — Vol. 2 , iss. 1 . — S. 293–310 . — ISSN 2329-9061 2329-907X, 2329-9061 . - doi : 10.2140/obs.2019.2.293 .
5. ↑ David Harvey, Joris Van Der Hoeven. Heltalsmultiplikation i tiden O(n log n  ) . — 2019. Arkiverad 8 april 2019 på Wayback Machine
6. ↑ Erica Klarreich. Multiplikation når hastighetsgränsen  //  Kommunikation av ACM. - 2019. - 20 december. - doi : 10.1145/3371387 . Arkiverad från originalet den 30 juni 2020.