Multiplication algorithm: Difference between revisions

Content deleted Content added
m cat
Cxxl (talk | contribs)
added links to schönhage and schönahge-strassen
Line 26:
Another Method of multiplication is called Toom-Cook or [[Toom3]]
 
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 19721971 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.