Multiplication algorithm: Difference between revisions

Revision as of 17:55, 28 July 2022

Revision as of 18:00, 28 July 2022

Line 248:

{{Anchor|Computational complexity}}

{{unsolved|computer science|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}

{{merge from|Fürer's algorithm|discuss=Talk:Multiplication algorithm#Merger proposal|date=February 2022}}

===Karatsuba multiplication===

Line 297 ⟶ 296:

==== Further improvements ====

In 2007 the [[asymptotic complexity]] of integer multiplication was improved by the Swiss mathematician [[Martin Fürer]] of Pennsylvania State University to ''n''&nbsp;log(''n'')&nbsp;2^{Θ([[iterated logarithm|log^*]](''n''))} using Fourier transforms over complex numbers.<ref name="fürer_1">Fürer, M. (2007). "[https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf Faster Integer Multiplication]" in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11–13, 2007, San Diego, California, USA</ref> Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi gave a similar algorithm using [[modular arithmetic]] in 2008 achieving the same running time.<ref>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> In context of the above material, what these latter authors have achieved is to find ''N'' much less than 2^3''k'' + 1, so that ''Z''/''NZ'' has a (2''m'')th root of unity. This speeds up computation and reduces the time complexity. The difference between the <math>\log\log n</math> and <math>2^{\log^* n}</math> terms, from a complexity point of view, is asymptotically in the advantage of Fürer's algorithm for integers greater than <math>2^{2^{64}}</math>. However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs.

In 2015, Harvey, [[Joris van der Hoeven]] and Lecerf<ref>D. Harvey, J. van der Hoeven and G. Lecerf (2015). "Even faster integer multiplication", February 2015. {{arXiv|1407.3360}}</ref> gave a new algorithm that achieves a running time of <math>O(n\log n \cdot 2^{3\log^* n})</math>, making explicit the implied constant in the <math>O(\log^* n)</math> exponent. They also proposed a variant of their algorithm which achieves <math>O(n\log n \cdot 2^{2\log^* n})</math> but whose validity relies on standard conjectures about the distribution of [[Mersenne prime]]s. In 2016, Covanov and Thomé proposed an integer multiplication algorithm based on a generalization of [[Fermat primes]] that conjecturally achieves a complexity bound of <math>O(n\log n \cdot 2^{2\log^* n})</math>. This matches the 2015 conditional result of Harvey, van der Hoeven, and Lecerf but uses a different algorithm and relies on a different conjecture.<ref>{{cite journal |first1=Svyatoslav |last1=Covanov |first2=Emmanuel |last2=Thomé |title=Fast Integer Multiplication Using Generalized Fermat Primes |journal=[[Mathematics of Computation|Math. Comp.]] |volume=88 |year=2019 |issue=317 |pages=1449–1477 |doi=10.1090/mcom/3367 |arxiv=1502.02800 |s2cid=67790860 }}</ref> In 2018, Harvey and van der Hoeven used an approach based on the existence of short lattice vectors guaranteed by [[Minkowski's theorem]] to prove an unconditional complexity bound of <math>O(n\log n \cdot 2^{2\log^* n})</math>.<ref>D. Harvey and J. van der Hoeven (2018). "Faster integer multiplication using short lattice vectors", February 2018. {{arXiv|1802.07932}}</ref>