Content deleted Content added
added links to schönhage and schönahge-strassen |
Added brief description of the Toom-Cook method |
||
Line 24:
It is possible to experimentally verify whether a given system uses Karatsuba's method or long multiplication: take your favorite two 100,000 digit numbers, multiply them and measure the time it takes. Then take your favorite two 200,000 digit numbers and measure the time it takes to multiply those. If Karatsuba's method is being used, the second time will be about three times as long as the first; if long multiplication is being used, it will be about four times as long.
Another Method of multiplication is called Toom-Cook or [[Toom3]]. The Toom-Cook method splits each number to be multiplied into multiple parts. Karatsuba is a special case of Toom-Cook using two parts. A three-way Toom-Cook can do a size-N<sup>3</sup> multiplication for the cost of five size-N multiplications, improvement by a factor of 9/5 compared to the Karatsuba method's improvement by a factor of 4/3. Using more parts eventually comes up against the law of diminishing returns.
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.
| |||