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[1] 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.[2]

Context modificare

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

Algoritmi îmbunătățiți modificare

Î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.[3] S-a estimat că acesta devine mai rapid decât algoritmul Schönhage–Strassen pentru numere mai mari de  .[4]

În 2015 Harvey, Joris van der Hoeven și Lecerf[5] au propus un nou algoritm care atinge un timp de funcționare de   făcând explicită constanta implicită din exponentul  . Ei au propus și o variantă a algoritmului lor care realizează   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.[6] Din păcate este la fel de nepractic ca toate celelalte implementări ale acestui algoritm.[7][8]

Î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  . 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ă.[9]

Î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  .[10]

În martie 2019, Harvey și van der Hoeven au publicat un algoritm de înmulțire a numerelor întregi mult căutat, de complexitate  , despre care s-a conjecturat că este asimptotic optim.[11][12] 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.”[13]

Note modificare

  1. ^ a b M. Fürer (2007), "Faster Integer Multiplication" Proceedings of the 39th annual ACM Symposium on Theory of Computing (STOC), 55–67, San Diego, CA, June 11–13, 2007, and SIAM Journal on Computing, Vol. 39 Issue 3, 979–1005, 2009.
  2. ^ de Schönhage, A.; Strassen, V. (). „Schnelle Multiplikation großer Zahlen”. Computing. 7 (3–4): 281–292. doi:10.1007/BF02242355. 
  3. ^ en A. De, C. Saha, P. Kurur and R. Saptharishi (2008). "Fast integer multiplication using modular arithmetic" Proceedings of the 40th annual ACM Symposium on Theory of Computing (STOC), 499–506, New York, NY, 2008, and SIAM Journal on Computing, Vol. 42 Issue 2, 685–699, 2013. arΧiv:0801.1416
  4. ^ en Lüders, Christoph (). Implementation of the DKSS Algorithm for Multiplication of Large Numbers (PDF). International Symposium on Symbolic and Algebraic Computation. pp. 267–274. Arhivat din original (pdf) la . Accesat în . 
  5. ^ en D. Harvey, J. van der Hoeven, G. Lecerf (2015), "Even faster integer multiplication", February 2015. arΧiv:1407.3360
  6. ^ en Covanov, S.; Thomé, E. (). „Fast Arithmetic for Faster Integer Multiplication”. arXiv:1502.02800v1 .  Published as Covanov & Thomé (2019)
  7. ^ en S. Covanov and E. Thomé (2014). "Efficient implementation of an algorithm multiplying big numbers", Internal research report, Polytechnics School, France, July 2014
  8. ^ en S. Covanov and M. Moreno Mazza (2015). "Putting Fürer algorithm into practice", Master research report, Polytechnics School, France, January 2015
  9. ^ en Covanov, Svyatoslav; Thomé, Emmanuel (). „Fast Integer Multiplication Using Generalized Fermat Primes”. Mathematics of Computation. 88: 1449–1477. arXiv:1502.02800 . doi:10.1090/mcom/3367. 
  10. ^ en D. Harvey and J. van der Hoeven (2018). "Faster integer multiplication using short lattice vectors", February 2018. arΧiv:1802.07932
  11. ^ en Harvey, David; Van Der Hoeven, Joris (). Integer multiplication in time O(n log n). 
  12. ^ en Hartnett, Kevin (). „Mathematicians Discover the Perfect Way to Multiply”. Wired. ISSN 1059-1028. Accesat în . 
  13. ^ en Gilbert, Lachlan (). „Maths whiz solves 48-year-old multiplication problem”. UNSW. Accesat în .