Karatsuba algorithm: Difference between revisions

Revision as of 21:47, 8 June 2008

Revision as of 19:45, 11 June 2008

Line 48:

for some constants ''c'' and ''d'', and this [[recurrence relation]] can be solved using the [[master theorem]], giving a time complexity of Θ(''n''^{log(3)/log(2)}). The number log(3)/log(2) is approximately 1.585, so this method is significantly faster than [[long multiplication]] as ''n'' grows large. Because of the overhead of recursion, however, Karatsuba's multiplication is typically slower than long multiplication for small values of ''n''; typical implementations therefore switch to long multiplication if ''n'' is below some threshold when computing the subproducts.

Implementations differ greatly on what the crossover point is when Karatsuba becomes faster than the classical algorithm, but generally numbers over 2³²⁰ are faster with Karatsuba. [http://gmplib.org/manual/Karatsuba-Multiplication.html][http://ozark.hendrix.edu/~burch/proj/karat/comment1.html] [[Toom-CookToom–Cook multiplication]] is a faster generalization of Karatsuba's, and is further surpassed by the [[Schönhage-Strassen algorithm]].

==References==