Harvey-van der Hoeven algoritmus

A Harvey-van der Hoeven algoritmus kétbites egész számok időbonyolultságú szorzására szolgáló algoritmus a többszalagos Turing-gép modellben . David Harvey matematikusok, az Új-Dél-Wales Egyetemről és Joris van der Hoeven , a Francia Nemzeti Tudományos Kutatási Központtól javasolták . 2020-tól ez a leggyorsabb ismert algoritmus a számok szorzására ebben a modellben, míg a szorzóalgoritmusok időbonyolultságának becslése javíthatatlannak tűnik. $n$ $O(n\log n)$ $O(n\log n)$

Történelem

Az egész számok szorzására szolgáló gyors algoritmusok létezésének kérdése fontos helyet foglal el a számítási komplexitás elméletében . A legismertebb szorzási módszerek, mint például a halmozott szorzás, számtani műveleteket igényelnek. Ezt a becslést először 1960-ban Anatolij Karatsuba javította , aki egy algoritmust javasolt a futásidővel való szorzáshoz [1] . 1971-ben Schönhage és Strassen egy olyan algoritmust javasolt, amely a gyors Fourier-transzformáción alapul [2] . Ugyanebben a munkában azt a hipotézist állítottak fel, hogy az optimális szorzási algoritmushoz elemi műveletek szükségesek. A Schönhage és Strassen algoritmus által megadott felső korlát azonban sokáig javulás nélkül maradt. Csak 2007-ben, 36 évvel később Martin Fuhrer javasolt egy algoritmust futási idővel egy meghatározatlan állandóhoz , ahol egy iterált logaritmus [3] . Ezt követően Harvey és van der Hoeven ezt a becslést először [4] -re , majd -ra javította, ezzel megerősítve a Schönhage és Strassen [5] sejtésében felállított felső korlátot . Az algoritmusnak nagy elméleti jelentősége van, mivel a többszalagos Turing-gép modellben a számszorzó algoritmusok futásidejének hipotetikus alsó korlátját éri el. Gyakorlati gyorsulás azonban csak olyan számokon érhető el, amelyek bináris hossza meghaladja a bitet, míg a részecskék számát a megfigyelhető univerzumban [6] -ra becsülik . $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}}\kb. 2^{7\cdot 10^{38}}$ $2^{270}$

Jegyzetek

↑ A. Karatsuba, Y. Offman. Többértékű számok szorzása automatákon // Dokl. A Szovjetunió Tudományos Akadémia. - 1962. - február 9. ( 145. köt. , 2. szám ). - S. 293-294 .
↑ A. Schönhage, V. Strassen. Schnelle Multiplikation großer Zahlen (német) // Számítástechnika. — 1971-09-01. — bd. 7 , H. 3 . – S. 281–292 . — ISSN 1436-5057 . - doi : 10.1007/BF02242355 .
↑ Martin Furer. Gyorsabb egész szám szorzás (angol) // SIAM Journal on Computing. — 2009-01. — Vol. 39 , iss. 3 . — P. 979–1005 . - ISSN 1095-7111 0097-5397, 1095-7111 . - doi : 10.1137/070711761 .
↑ David Harvey, Joris van der Hoeven. Gyorsabb egész számok szorzása rövid rácsvektorok segítségével // The Open Book Series. — 2019-01-28. — Vol. 2 , iss. 1 . — P. 293–310 . — ISSN 2329-9061 2329-907X, 2329-9061 . - doi : 10.2140/obs.2019.2.293 .
↑ David Harvey, Joris Van Der Hoeven. Egész szám szorzása O(n log n ) időben . — 2019. Archiválva : 2019. április 8. a Wayback Machine -nél
↑ Erica Klarreich. A szorzás elérte a sebességkorlátozást // Az ACM kommunikációja. - 2019. - december 20. - doi : 10.1145/3371387 . Archiválva az eredetiből: 2020. június 30.

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus