Editing Multiplication (section)

===Computer algorithms===
{{Main|Multiplication algorithm#Fast multiplication algorithms for large inputs}}
The classical method of multiplying two {{math|''n''}}-digit numbers requires {{math|''n''<sup>2</sup>}} digit multiplications. [[Multiplication algorithm]]s have been designed that reduce the computation time considerably when multiplying large numbers. Methods based on the [[Discrete Fourier transform#Multiplication of large integers|discrete Fourier transform]] reduce the [[computational complexity]] to {{math|''O''(''n'' log ''n'' log log ''n'')}}. In 2016, the factor {{math|log log ''n''}} was replaced by a function that increases much slower, though still not constant.<ref>{{Cite journal|last1=Harvey|first1=David|last2=van der Hoeven|first2=Joris|last3=Lecerf|first3=Grégoire|title=Even faster integer multiplication|date=2016|journal=Journal of Complexity|volume=36|pages=1–30|doi=10.1016/j.jco.2016.03.001|issn=0885-064X|arxiv=1407.3360|s2cid=205861906}}</ref> In March 2019, David Harvey and Joris van der Hoeven submitted a paper presenting an integer multiplication algorithm with a complexity of <math>O(n\log n).</math><ref>David Harvey, Joris Van Der Hoeven (2019). [https://hal.archives-ouvertes.fr/hal-02070778 Integer multiplication in time O(n log n)] {{Webarchive|url=https://web.archive.org/web/20190408180939/https://hal.archives-ouvertes.fr/hal-02070778 |date=2019-04-08 }}</ref> The algorithm, also based on the fast Fourier transform, is conjectured to be asymptotically optimal.<ref>{{Cite web|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|website=Quanta Magazine|date=11 April 2019|language=en|access-date=2020-01-25}}</ref> The algorithm is not practically useful, as it only becomes faster for multiplying extremely large numbers (having more than {{math|2<sup>1729<sup>12</sup></sup>}} bits).<ref>{{Cite web|url=https://cacm.acm.org/magazines/2020/1/241707-multiplication-hits-the-speed-limit/fulltext|title=Multiplication Hits the Speed Limit|last=Klarreich|first=Erica|website=cacm.acm.org|date=January 2020 |language=en|access-date=2020-01-25|archive-url=https://archive.today/20201031123457/https://cacm.acm.org/magazines/2020/1/241707-multiplication-hits-the-speed-limit/fulltext|archive-date=2020-10-31|url-status=live}}</ref>