Multiplication algorithm: Difference between revisions

Revision as of 07:53, 30 November 2011

Revision as of 07:42, 17 December 2011

Line 360:

#Computing the inverse Fourier transform and

#Adding the part of ''c''_''k'' that is greater than 2^''w'' to ''c''_''k''+1.

Another way to describe this process is forming polynomials whose coefficients are the digits of the inputs (in base 2^''w''), multiplying them rapidly using convolution by FFT, then extracting the coefficients of the result polynomial and performing carrying.

The [[Schönhage–Strassen algorithm]], described in 1971 by [[Arnold Schönhage|Schönhage]] and Strassen, 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]]) 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. 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.

FFT-based algorithms multiply [[Polynomial|polynomials]], not numbers. But it is trivial to convert a number to the corresponding polynomial and then restore resulting number from the polynomial.

===Linear time multiplication===