Content deleted Content added
m cat |
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
|