Multiplication algorithm

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^3”k” + 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.

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^3”k” + 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.

In March 2019, [[David Harvey (mathematician)|David Harvey]] and [[Joris van der Hoeven]] announced their discovery of an {{nowrap|”O”(”n” log ”n”)}} multiplication algorithm.<ref>{{Cite magazine|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|magazine=Quanta Magazine|date=11 April 2019|access-date=2019-05-03}}</ref> It was published in the ”[[Annals of Mathematics]]” in 2021.<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 $O(n \log n)$ | volume = 193 | year = 2021}}</ref>

In March 2019, [[David Harvey (mathematician)|David Harvey]] and [[Joris van der Hoeven]] announced their discovery of an {{nowrap|”O”(”n” log ”n”)}} multiplication algorithm.<ref>{{Cite magazine|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|magazine=Quanta Magazine|date=11 April 2019|access-date=2019-05-03}}</ref> It was published in the ”[[Annals of Mathematics]]” in 2021.<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>

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 {{nowrap|”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. {{nowrap|1=”k” = 2³¹ − 1}} supports transform sizes up to 2³².

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 {{nowrap|”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. {{nowrap|1=”k” = 2³¹ − 1}} supports transform sizes up to 2³².