Content deleted Content added
Grammarbot (talk | contribs) m Removed space before comma. I am a bot. Please revert my change if it was incorrect. I will notice automatically. |
"Removed extra blank lines." |
||
Line 27:
There exist even faster algorithms, based on the '''[[fast Fourier transform]]'''. The idea, due to [[Volker Strassen|Strassen]] (1968), is the following: multiplying two numbers represented as digit strings is virtually the same as computing the [[convolution]] of those two digit strings. Instead of computing a convolution, one can instead first compute the [[discrete Fourier transform]]s, multiply them entry by entry, and then compute the inverse Fourier transform of the result. (See [[convolution theorem]].) The fastest known method based on this idea was described in 1971 by [[Arnold Schönhage|Schönhage]] and [[Strassen]] ([[Schönhage-Strassen algorithm]]) and has a time complexity of Θ(''n'' ln(''n'') ln(ln(''n''))). The [[GIMPS]] distributed Internet [[prime number|prime]] search project deals with numbers having several million digits and employs a Fourier transform based multiplication algorithm. Using [[number-theoretic transform]]s instead of discrete Fourier transforms should avoid any [[rounding error]] problems by using [[modular arithmetic]] instead of [[complex number]]s.
All the above multiplication algorithms can also be used to multiply [[polynomial]]s.
|