Karatsuba algorithm: Difference between revisions

Revision as of 16:36, 26 March 2007

Revision as of 19:41, 16 April 2007

Line 49:

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://wwwgmplib.swox.com/gmporg/manual/Karatsuba-Multiplication.html][http://ozark.hendrix.edu/~burch/proj/karat/comment1.html] [[Toom-Cook multiplication]] is a faster generalization of Karatsuba's, and is further surpassed by the fastest known, the [[Schönhage-Strassen algorithm]].

<!--