Content deleted Content added
No edit summary |
PierreAbbat (talk | contribs) Fourier multiplication GIMPS |
||
Line 22:
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.
There exist even faster algorithms, but they 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. These algorithms are based on the [[fast Fourier transform]]. The idea 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 methods have a time complexity of O(''n'' ln(''n'') ln(ln(''n''))). This method is used in the [[GIMPS]].
All the above multiplication algorithms can also be used to multiply [[polynomial]]s.
| |||