Algoritmul Fürer

Algoritmul Fürer este un algoritm de înmulțire a numerelor întregi pentru numere întregi extrem de mari, cu complexitate foarte mică. A fost publicat în 2007 de matematicianul elvețian Martin Fürer de la Universitatea de Stat din Pennsylvania ca un algoritm mai rapid asimptotic atunci când este analizat pe o mașină Turing cu mai multe benzi decât predecesorul său, algoritmul Schönhage–Strassen.

Context

Algoritmul Schönhage–Strassen folosește transforma Fourier rapidă (FFT) pentru a calcula produsele întregi în timp $O(n\log n\cdot \log \log n)$, iar autorii săi, Arnold Schönhage și Volker Strassen, presupun o limită inferioară de $\Omega (n\log n)$. Algoritmul Fürer reduce decalajul dintre aceste două limite. Poate fi folosit pentru a înmulți numere întregi de lungime $n$ în timpul $O\left(n\log n\ \cdot 2^{O(\log ^{*}n)}\right)$ unde log*n este logaritmul iterat. Din punct de vedere al complexității, diferența dintre termenii $\log \log n$ și $2^{\log ^{*}n}$ este asimptotic în favoarea algoritmului Fürer pentru întregi mai mari ca $2^{2^{64}}$. Totuși, pentru valorile realiste a lui n diferența dintre acești termeni este foarte mică.

Algoritmi îmbunătățiți

În 2008 De ș.a. au dat un algoritm similar care se bazează pe aritmetica modulară în loc de aritmetica complexă pentru a atinge de fapt același timp de funcționare. S-a estimat că acesta devine mai rapid decât algoritmul Schönhage–Strassen pentru numere mai mari de $10^{10^{4796}}$.

În 2015 Harvey, Joris van der Hoeven și Lecerf au propus un nou algoritm care atinge un timp de funcționare de $O(n\log n\cdot 2^{3\log ^{*}n})$ făcând explicită constanta implicită din exponentul $O(\log ^{*}n)$. Ei au propus și o variantă a algoritmului lor care realizează $O(n\log n\cdot 2^{2\log ^{*}n})$ dar a cărui validitate se bazează pe presupuneri standard despre distribuția [[număr prim Mersenne |numerelor prime Mersenne].

În 2015 Covanov și Thomé au prezentat o altă modificare a algoritmului Fürer, care atinge același timp de funcționare. Din păcate este la fel de nepractic ca toate celelalte implementări ale acestui algoritm.

În 2016 Covanov și Thomé au propus un algoritm de înmulțire al numerelor întregi bazat pe o generalizare a numerelor prime Fermat, despre care s-a conjecturat că atinge o complexitate limită de $O(n\log n\cdot 2^{2\log ^{*}n})$. Aceasta se potrivește cu rezultatul condiționat din 2015 al lui Harvey, van der Hoeven și Lecerf, dar folosește un algoritm diferit și se bazează pe o conjectură diferită.

În 2018 Harvey și van der Hoeven au folosit o abordare bazată pe existența unor vectori latice scurte garantați de teorema Minkowski pentru a demonstra o complexitate necondiționată limită de $O(n\log n\cdot 2^{2\log ^{*}n})$.

În martie 2019, Harvey și van der Hoeven au publicat un algoritm de înmulțire a numerelor întregi mult căutat, de complexitate $O(n\log n)$, despre care s-a conjecturat că este asimptotic optim. Deoarece Schönhage și Strassen au prezis că n log(n) este cel mai bun rezultat posibil, Harvey a spus: „...se așteaptă ca munca noastră să fie sfârșitul drumului în această problemă, deși nu știm încă cum să demonstrăm asta riguros.”