Content deleted Content added
→Computational complexity of multiplication: adding a lead |
|||
Line 248:
{{Anchor|Computational complexity}}
{{unsolved|computer science|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}
A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of matrix multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).
The algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only {{nowrap|''O''(''n'' log ''n'')}} operations.<ref>{{cite journal | last1 = Harvey | first1 = David | last2 = van der Hoeven | first2 = Joris | author2-link = Joris van der Hoeven | doi = 10.4007/annals.2021.193.2.4 | issue = 2 | journal = [[Annals of Mathematics]] | mr = 4224716 | pages = 563–617 | series = Second Series | title = Integer multiplication in time <math>O(n \log n)</math> | volume = 193 | year = 2021}}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.
===Karatsuba multiplication===
Line 271 ⟶ 275:
Although using more and more parts can reduce the time spent on recursive multiplications further, the overhead from additions and digit management also grows. For this reason, the method of Fourier transforms is typically faster for numbers with several thousand digits, and asymptotically faster for even larger numbers.
===Schönhage–Strassen===
{{Main|Schönhage–Strassen algorithm}}
[[File:Integer multiplication by FFT.svg|thumb|350px|Demonstration of multiplying 1234 × 5678 = 7006652 using fast Fourier transforms (FFTs). [[Number-theoretic transform]]s in the integers modulo 337 are used, selecting 85 as an 8th root of unity. Base 10 is used in place of base 2<sup>''w''</sup> for illustrative purposes.]]
The basic idea due to [[Volker Strassen|Strassen]] (1968) is to use fast polynomial multiplication to perform fast integer multiplication. The algorithm was made practical and theoretical guarantees were provided in 1971 by [[Arnold Schönhage|Schönhage]] and Strassen resulting in the [[Schönhage–Strassen algorithm]].<ref name="schönhage">A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", ''Computing'' '''7''' (1971), pp. 281–292.</ref> The details are the following: We choose the largest integer ''w'' that will not cause [[Integer overflow|overflow]] during the process outlined below. Then we split the two numbers into ''m'' groups of ''w'' bits as follows
Line 295 ⟶ 300:
The algorithm has a time complexity of [[Bachmann-Landau notation|Θ]](''n'' log(''n'') log(log(''n''))) and is used in practice for numbers with more than 10,000 to 40,000 decimal digits.
In 2007 the [[asymptotic complexity]] of integer multiplication was improved by the Swiss mathematician [[Martin Fürer]] of Pennsylvania State University to ''n'' log(''n'') 2<sup>Θ([[iterated logarithm|log<sup>*</sup>]](''n''))</sup> 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<sup>3''k''</sup> + 1, so that ''Z''/''NZ'' has a (2''m'')th root of unity. This speeds up computation and reduces the time complexity. However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs.
| |||