Harvey-van der Hoeven algoritme

Harvey-van der Hoeven-  algoritmen er en algoritme til at multiplicere to - bit-heltal med tidskompleksitet i multitape Turing-maskinemodellen . Foreslået af matematikerne David Harvey fra University of New South Wales og Joris van der Hoeven fra det franske nationale center for videnskabelig forskning . Fra 2020 er det den hurtigste kendte algoritme til at multiplicere tal i denne model, mens estimatet for tidskompleksiteten af ​​multiplikationsalgoritmer ser ud til at være uforbedret.

Historie

Spørgsmålet om eksistensen af ​​hurtige algoritmer til multiplikation af heltal indtager en vigtig plads i teorien om beregningsmæssig kompleksitet . De mest kendte multiplikationsmetoder, såsom stablet multiplikation, kræver aritmetiske operationer. Dette skøn blev første gang forbedret i 1960 af Anatoly Karatsuba , som foreslog en algoritme til multiplikation med køretid [1] . I 1971 foreslog Schönhage og Strassen en algoritme baseret på den hurtige Fourier-transformation over tid [2] . I samme arbejde fremsætter de en hypotese om, at den optimale multiplikationsalgoritme kræver elementære operationer. Men i lang tid forblev den øvre grænse givet af Schönhage og Strassen-algoritmen uden forbedring. Først i 2007, 36 år senere, foreslog Martin Fuhrer en algoritme med køretid for en uspecificeret konstant , hvor  er en itereret logaritme [3] . Efterfølgende forbedrede Harvey og van der Hoeven dette estimat først til [4] , og derefter til , hvilket bekræftede den øvre grænse, der blev fremsat i Schönhages og Strassens formodning [5] . Algoritmen er af stor teoretisk betydning, da den opnår en hypotetisk nedre grænse for køretiden for talmultiplikationsalgoritmer i multitape Turing-maskinemodellen. Praktisk acceleration opnås dog kun på tal, hvis binære længde overstiger en smule, mens antallet af partikler i det observerbare univers estimeres til [6] .

Noter

1. ↑ A. Karatsuba, Y. Offman. Multiplikation af tal med flere værdier på automater  // Dokl. USSR's Videnskabsakademi. - 1962. - 9. februar ( bind 145 , nr. 2 ). - S. 293-294 .
2. ↑ A. Schönhage, V. Strassen. Schnelle Multiplikation großer Zahlen  (tysk)  // Computing. — 1971-09-01. — bd. 7 , H. 3 . — S. 281–292 . — ISSN 1436-5057 . - doi : 10.1007/BF02242355 .
3. ↑ Martin Furer. Hurtigere heltalsmultiplikation  (engelsk)  // SIAM Journal on Computing. - 2009-01. — Bd. 39 , udg. 3 . — S. 979–1005 . - ISSN 1095-7111 0097-5397, 1095-7111 . - doi : 10.1137/070711761 .
4. ↑ David Harvey, Joris van der Hoeven. Hurtigere heltalsmultiplikation ved hjælp af korte gittervektorer  //  The Open Book Series. — 2019-01-28. — Bd. 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. Heltals multiplikation i tid O(n log n  ) . — 2019. Arkiveret 8. april 2019 på Wayback Machine
6. ↑ Erica Klarreich. Multiplikation rammer hastighedsgrænsen  //  Kommunikation af ACM. - 2019. - 20. december. - doi : 10.1145/3371387 . Arkiveret fra originalen den 30. juni 2020.