Multiplication algorithm: Difference between revisions

Revision as of 04:22, 6 January 2004

Revision as of 19:53, 6 January 2004

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/Strassen and has a time complexity of Θ(''n'' ln(''n'') ln(ln(''n''))). These approaches are not used in computer algebra systems and bignum libraries because they are difficult to implement and don't provide speed benefits for the sizes of numbers typically encountered in those systems. 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.