Harvey-van der Hoeven-algoritmi

Harvey-van der Hoeven-  algoritmi on algoritmi, jolla kerrotaan kaksibittiset kokonaisluvut aikakompleksisesti moninauhaisessa Turingin konemallissa . Ehdotuksen ovat esittäneet matemaatikot David Harvey New South Walesin yliopistosta ja Joris van der Hoeven Ranskan kansallisesta tieteellisestä tutkimuskeskuksesta . Vuodesta 2020 lähtien se on nopein tunnettu algoritmi lukujen kertomiseen tässä mallissa, kun taas kertolaskualgoritmien aikamonimutkaisuuden arvio näyttää olevan parantamaton.

Historia

Kysymys nopeiden algoritmien olemassaolosta kokonaislukujen kertomiseen on tärkeällä sijalla laskennallisen monimutkaisuuden teoriassa . Tunnetuimmat kertolaskumenetelmät, kuten pinottu kertolasku, vaativat aritmeettisia operaatioita. Tätä arviota paransi ensimmäisen kerran vuonna 1960 Anatoli Karatsuba , joka ehdotti algoritmia kertomiselle ajoajalla [1] . Vuonna 1971 Schönhage ja Strassen ehdottivat algoritmia , joka perustuu nopeaan Fourier-muunnokseen ajan myötä [2] . Samassa työssä he esittivät hypoteesin, että optimaalinen kertolaskualgoritmi vaatii alkeisoperaatioita. Pitkään Schönhagen ja Strassenin algoritmin antama yläraja pysyi kuitenkin parantumattomana. Vasta vuonna 2007, 36 vuotta myöhemmin, Martin Fuhrer ehdotti algoritmia , jossa on ajoaika määrittelemättömälle vakiolle , jossa  on iteroitu logaritmi [3] . Myöhemmin Harvey ja van der Hoeven paransivat tätä arviota ensin arvoon [4] ja sitten arvoon , mikä vahvisti Schönhagen ja Strassenin [5] olettamuksessa esitetyn ylärajan . Algoritmilla on suuri teoreettinen merkitys, koska se saavuttaa hypoteettisen alarajan lukujen kertolaskualgoritmien käyntiajalle moninauhaisessa Turingin konemallissa. Käytännön kiihtyvyys saavutetaan kuitenkin vain luvuilla, joiden binääripituus ylittää bitin, kun taas havaittavissa olevan universumin hiukkasten lukumääräksi arvioidaan [6] .

Muistiinpanot

1. ↑ A. Karatsuba, Y. Offman. Moniarvoisten lukujen kertominen automaateissa  // Dokl. Neuvostoliiton tiedeakatemia. - 1962. - 9. helmikuuta ( nide 145 , nro 2 ). - S. 293-294 .
2. ↑ A. Schönhage, V. Strassen. Schnelle Multiplikation großer Zahlen  (saksa)  // Computing. - 1971-09-01. - bd. 7 , H. 3 . — S. 281–292 . — ISSN 1436-5057 . - doi : 10.1007/BF02242355 .
3. ↑ Martin Furer. Nopeampi kokonaislukukerto  (englanti)  // SIAM Journal on Computing. - 2009-01. — Voi. 39 , iss. 3 . — s. 979–1005 . - ISSN 1095-7111 0097-5397, 1095-7111 . - doi : 10.1137/070711761 .
4. ↑ David Harvey, Joris van der Hoeven. Nopeampi kokonaislukujen kertolasku lyhyillä hilavektoreilla  //  Open Book Series. - 28-01-2019 — Voi. 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. Kokonaisluvun kertolasku ajassa O(n log n  ) . — 2019. Arkistoitu 8. huhtikuuta 2019 Wayback Machinessa
6. ↑ Erica Klarreich. Kertominen ylittää nopeusrajoituksen  //  ACM:n tiedonsiirto. - 2019 - 20. joulukuuta. - doi : 10.1145/3371387 . Arkistoitu alkuperäisestä 30.6.2020.