Content deleted Content added
fft-based multiplication is used in GMP |
m lks |
||
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 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 1972 by Schönhage and [[Strassen]] 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.
Line 47:
[[Ruby programming language|Ruby]], and
[[Common Lisp]].
See also: [[Strassen algorithm]].
==External links==
| |||