Vizualizare sursă pentru „Algoritmul Fürer”

'''Algoritmul Fürer''' este un [[algoritm]] de [[înmulțire (matematică)|înmulțire]] a [[număr întreg|numerelor întregi]] pentru numere întregi extrem de mari, cu [[teoria complexității |complexitate]] foarte mică. A fost publicat în 2007 de [[matematician]]ul [[elveția]]n [[Martin Fürer]] de la Universitatea de Stat din Pennsylvania<ref name="fürer_1">M. Fürer (2007), "[https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf 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.</ref> 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]].<ref>{{de icon}} {{cite journal |first=A. |last=Schönhage |first2=V. |last2=Strassen |year=1971 |title=Schnelle Multiplikation großer Zahlen |journal=Computing |volume=7 |issue=3–4 |pages=281–292 |doi=10.1007/BF02242355}}</ref>

== Context ==
Algoritmul Schönhage–Strassen folosește [[transforma Fourier rapidă]] (FFT) pentru a calcula produsele întregi în timp <math>O (n \log n \cdot \log \log n)</math>, iar autorii săi, [[Arnold Schönhage]] și [[Volker Strassen]], presupun o limită inferioară de {{nowrap|<math>\Omega(n \log n)</math>.}} Algoritmul Fürer reduce decalajul dintre aceste două limite. Poate fi folosit pentru a înmulți numere întregi de lungime <math>n</math> în timpul <math style="vertical-align:-15%">O \left(n \log n\ \cdot 2^{O(\log^* n)} \right)</math> unde {{nowrap|{{log-star}}''n''}} este [[logaritm iterat |logaritmul iterat]]. Din punct de vedere al complexității, diferența dintre termenii <math>\log\log n</math> și <math>2^{\log^* n}</math> este asimptotic în favoarea algoritmului Fürer pentru întregi mai mari ca <math>2^{2^{64}}</math>. Totuși, pentru valorile realiste a lui {{mvar|n}} diferența dintre acești termeni  este foarte mică.<ref name="fürer_1" />

== Algoritmi îmbunătățiți ==
În 2008 De ''ș.a.'' au dat un algoritm similar care se bazează pe [[modulo|aritmetica modulară]] în loc de aritmetica complexă pentru a atinge de fapt același timp de funcționare.<ref>{{en icon}} 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. {{arxiv|0801.1416}}</ref> S-a estimat că acesta devine mai rapid decât algoritmul Schönhage–Strassen pentru numere mai mari de <math>10^{10^{4796}}</math>.<ref>{{en icon}} {{cite conference|first=Christoph|last=Lüders|title=Implementation of the DKSS Algorithm for Multiplication of Large Numbers|format=pdf|conference=International Symposium on Symbolic and Algebraic Computation|pages=267-274|date=2015|url=http://wrogn.com/wp-content/uploads/2015/07/ISSAC-2015-Lueders-Implementation-DKSS.pdf|access-date=2021-06-05|archive-date=2021-06-05|archive-url=https://web.archive.org/web/20210605035547/http://wrogn.com/wp-content/uploads/2015/07/ISSAC-2015-Lueders-Implementation-DKSS.pdf|dead-url=yes}}</ref>

În 2015 Harvey, [[Joris van der Hoeven]] și Lecerf<ref>{{en icon}} D. Harvey, J. van der Hoeven, G. Lecerf (2015), "Even faster integer multiplication", February 2015. {{arxiv|1407.3360}}</ref> au propus un nou algoritm care atinge un timp de funcționare de <math>O(n\log n \cdot 2^{3\log^* n})</math> făcând explicită constanta implicită din exponentul <math>O(\log^* n)</math>. Ei au propus și o variantă a algoritmului lor care realizează <math>O(n\log n \cdot 2^{2\log^* n})</math> 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.<ref>{{en icon}} {{cite paper |first=S. |last=Covanov |first2=E. |last2=Thomé |year=2015 |title=Fast Arithmetic for Faster Integer Multiplication |arxiv=1502.02800v1 }} Published as {{harvtxt|Covanov|Thomé|2019}}</ref> Din păcate este la fel de nepractic ca toate celelalte implementări ale acestui algoritm.<ref>{{en icon}} S. Covanov and E. Thomé (2014). "Efficient implementation of an algorithm multiplying big numbers", Internal research report, Polytechnics School, France, July 2014</ref><ref>{{en icon}} S. Covanov and M. Moreno Mazza (2015). "Putting Fürer algorithm into practice", Master research report, Polytechnics School, France, January 2015</ref>

În 2016 Covanov și Thomé au propus un algoritm de înmulțire al numerelor întregi bazat pe o generalizare a [[număr prim Fermat |numerelor prime Fermat]], despre care s-a conjecturat că atinge o complexitate limită de <math>O(n\log n \cdot 2^{2\log^* n})</math>. 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ă.<ref>{{en icon}} {{cite journal |first=Svyatoslav |last=Covanov |first2=Emmanuel |last2=Thomé |title=Fast Integer Multiplication Using Generalized Fermat Primes |journal=Mathematics of Computation |volume=88 |year=2019 |pages=1449–1477 |doi=10.1090/mcom/3367 |arxiv=1502.02800 }}</ref>

Î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 <math>O(n\log n \cdot 2^{2\log^* n})</math>.<ref>{{en icon}} D. Harvey and J. van der Hoeven (2018). "Faster integer multiplication using short lattice vectors", February 2018. {{arxiv|1802.07932}}</ref>

În martie 2019, Harvey și van der Hoeven au publicat un algoritm de înmulțire a numerelor întregi mult căutat, de complexitate <math>O(n\log n)</math>, despre care s-a conjecturat că este asimptotic optim.<ref>{{en icon}} {{Cite book|url=https://hal.archives-ouvertes.fr/hal-02070778|title=Integer multiplication in time O(n log n)|last=Harvey|first=David|last2=Van Der Hoeven|first2=Joris|date=2019-04-12}}</ref><ref>{{en icon}} {{Cite news|url=https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/|title=Mathematicians Discover the Perfect Way to Multiply|last=Hartnett|first=Kevin|date=2019-04-14|work=Wired|access-date=2019-04-15|issn=1059-1028}}</ref> Deoarece Schönhage și Strassen au prezis că ''n''&nbsp;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.”<ref>{{en icon}} {{cite news |last1=Gilbert |first1=Lachlan |title=Maths whiz solves 48-year-old multiplication problem |url=https://newsroom.unsw.edu.au/news/science-tech/maths-whiz-solves-48-year-old-multiplication-problem |access-date=18 April 2019 |publisher=UNSW |date=4 April 2019}}</ref>

== Note ==
<references responsive/>

{{Portal|Matematică}}

[[Categorie:Algoritmi|Furer]]