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.
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 .
Számelméleti algoritmusok | |
---|---|
Egyszerűség tesztek | |
Prímszámok keresése | |
Faktorizáció | |
Diszkrét logaritmus | |
GCD keresése | |
Modulo aritmetika | |
Számok szorzása és osztása | |
A négyzetgyök kiszámítása |