Multiplication algorithm: Difference between revisions

Revision as of 20:13, 3 May 2019

Revision as of 20:15, 3 May 2019

Line 358:

The algorithm has a time complexity of [[Bachmann-Landau notation|Θ]](''n''&nbsp;log(''n'')&nbsp;log(log(''n''))) and is used in practice for numbers with more than 10,000 to 40,000 decimal digits. In 2007 this was improved by Martin Fürer ([[Fürer's algorithm]]) <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> to give a time complexity of ''n''&nbsp;log(''n'')&nbsp;2^{Θ([[iterated logarithm|log^*]](''n''))} using Fourier transforms over complex numbers. Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi<ref>Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Fast Integer Multiplication Using Modular Arithmetic. Symposium on Theory of Computation (STOC) 2008.</ref> gave a similar algorithm using [[modular arithmetic]] in 2008 achieving the same running time. In context of the above material, what these latter authors have achieved is to find ''N'' much less than ''2^3k + 1'', so that ''Z/NZ'' has a ''2m^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.

In March 2019, [[David Harvey (mathematician)|David Harvey]] and [[De:Joris van der Hoeven]] ([[:de:Joris_van_der_Hoeven|Joris van der Hoevende]]) released a paper describing an <math>O(n \log n)</math>multiplication algorithm.<ref>David Harvey, Joris Van Der Hoeven. Integer multiplication in time O(n log n). 2019. ffhal-02070778</ref><ref>{{Cite web|url=https://rjlipton.wordpress.com/2019/03/29/integer-multiplication-in-nlogn-time/|title=Integer Multiplication in NlogN Time|last=KWRegan|date=2019-03-29|website=Gödel's Lost Letter and P=NP|language=en|access-date=2019-05-03}}</ref><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|access-date=2019-05-03}}</ref><ref>{{Cite web|url=https://web.maths.unsw.edu.au/~davidharvey/papers/nlogn/|title=Integer multiplication in time O(n log n)|last=Harvey|first=David|date=|website=|archive-url=|archive-date=|dead-url=|access-date=}}</ref>

Using [[number-theoretic transform]]s instead of [[discrete Fourier transform]]s avoids [[rounding error]] problems by using modular arithmetic instead of [[floating point|floating-point]] arithmetic. In order to apply the factoring which enables the FFT to work, the length of the transform must be factorable to small primes and must be a factor of ''N''-1, where ''N'' is the field size. In particular, calculation using a Galois Field GF(''k''²), where ''k'' is a [[Mersenne Prime]], allows the use of a transform sized to a power of 2; e.g. ''k'' = 2³¹-1 supports transform sizes up to 2³².