Multiplication algorithm: Difference between revisions

Revision as of 01:43, 14 September 2017

Revision as of 21:28, 2 November 2017

Line 365:

The ring ''Z/NZ'' would thus have a ''2m^th'' root of unity, namely 8. Also, it can be checked that ''c_k < N'', and thus no wrap around will occur.

The algorithm has a time complexity of Θ(''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). "[httphttps://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^{Θ(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.

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³².