Content deleted Content added
No edit summary |
m Reverted edits by 129.31.70.231 to last version by The Anome |
||
Line 34:
for some constants ''c'' and ''d'', and this [[recurrence relation]] can be solved, giving a time complexity of Θ(''n''<sup>ln(3)/ln(2)</sup>). The number ln(3)/ln(2) is approximately 1.585, so this method is significantly faster than long multiplication. Because of the overhead of recursion, Karatsuba's multiplication is not very fast for small values of ''n''; typical implementations therefore switch to long multiplication if ''n'' is below some threshold.
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.▼
▲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.
===Toom-Cook===
| |||