Algoritmus Harvey-van der Hoeven

Algoritmus Harvey-van der Hoeven je algoritmus pro násobení dvoubitových celých čísel s časovou složitostí v modelu multipáskového Turingova stroje . Navrhli to matematici David Harvey z University of New South Wales a Joris van der Hoeven z Francouzského národního centra pro vědecký výzkum . Od roku 2020 se jedná o nejrychlejší známý algoritmus pro násobení čísel v tomto modelu, přičemž odhad časové složitosti násobicích algoritmů se zdá být nezlepšitelný. $n$ $O(n\log n)$ $O(n\log n)$

Historie

Otázka existence rychlých algoritmů pro násobení celých čísel zaujímá důležité místo v teorii výpočetní složitosti . Nejznámější metody násobení, jako je vrstvené násobení, vyžadují aritmetické operace. Tento odhad byl poprvé zlepšen v roce 1960 Anatolym Karatsubou , který navrhl algoritmus pro násobení s dobou běhu [1] . V roce 1971 Schönhage a Strassen navrhli algoritmus založený na rychlé Fourierově transformaci v průběhu času [2] . Ve stejné práci předložili hypotézu, že optimální algoritmus násobení vyžaduje elementární operace. Po dlouhou dobu však horní hranice daná Schönhageovým a Strassenovým algoritmem zůstávala bez zlepšení. Teprve v roce 2007, o 36 let později, navrhl Martin Fuhrer algoritmus s dobou běhu pro blíže nespecifikovanou konstantu , kde je iterovaný logaritmus [3] . Následně Harvey a van der Hoeven zlepšili tento odhad nejprve na [4] a poté na , čímž potvrdili horní hranici předloženou v domněnce Schönhage a Strassena [5] . Algoritmus má velký teoretický význam, protože dosahuje hypotetické dolní meze pro dobu běhu algoritmů násobení čísel v modelu multipáskového Turingova stroje. Praktického zrychlení je však dosaženo pouze na číslech, jejichž binární délka přesahuje o bit, zatímco počet částic v pozorovatelném vesmíru se odhaduje jako [6] . $O(n^{2})$ $O(n^{\log _{2}3})$ $O(n\log n\log \log n)$ $O(n\log n)$ $O(n\log n\cdot K^{\log ^{*}n})$ $K>1$ $\log ^{*}n$ $O(n\log n\cdot 4^{\log ^{*}n})$ $O(n\log n)$ $2^{1729^{12}}\cca 2^{7\cdot 10^{38}}$ $2^{270}$

Poznámky

↑ A. Karatsuba, Y. Offman. Násobení vícehodnotových čísel na automatech // Dokl. Akademie věd SSSR. - 1962. - 9. února ( roč. 145 , č. 2 ). - S. 293-294 .
↑ A. Schönhage, V. Strassen. Schnelle Multiplikation großer Zahlen (německy) // Computing. — 1971-09-01. — bd. 7 , H. 3 . — S. 281–292 . — ISSN 1436-5057 . - doi : 10.1007/BF02242355 .
↑ Martin Furer. Faster Integer Multiplication (anglicky) // SIAM Journal on Computing. — 2009-01. — Sv. 39 , iss. 3 . — S. 979–1005 . - ISSN 1095-7111 0097-5397, 1095-7111 . - doi : 10.1137/070711761 .
↑ David Harvey, Joris van der Hoeven. Rychlejší celočíselné násobení pomocí krátkých mřížkových vektorů // The Open Book Series. — 28. 1. 2019. — Sv. 2 , iss. 1 . — S. 293–310 . — ISSN 2329-9061 2329-907X, 2329-9061 . - doi : 10.2140/obs.2019.2.293 .
↑ David Harvey, Joris Van Der Hoeven. Násobení celého čísla v čase O(n log n ) . — 2019. Archivováno 8. dubna 2019 na Wayback Machine
↑ Erica Klarreich. Násobení naráží na rychlostní limit // Komunikace ACM. - 2019. - 20. prosince. - doi : 10.1145/3371387 . Archivováno z originálu 30. června 2020.

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin