Karatsuba algorithm: Difference between revisions

Revision as of 12:21, 22 December 2006

Revision as of 12:22, 22 December 2006

Line 2:

==Example==

To multiply two ''n''-digit numbers ''x'' and ''y'' represented in base ''W'', where ''n'' is even and equal to 2''m'' (if ''n'' is odd instead, or the numbers are not of the same length, this can be corrected by adding zeros at the left end of ''x'' and/or ''y''), we can write

: ''x'' = ''x''₁ ''W''^''m'' + ''x''₂

: ''y'' = ''y''₁ ''W''^''m'' + ''y''₂

with ''m''-digit numbers ''x''₁, ''x''₂, ''y''₁ and ''y''₂. The product is given by

: ''xy'' = ''x''₁''y''₁ ''W''^2''m'' + (''x''₁''y''₂ + ''x''₂''y''₁) ''W''^''m'' + ''x''₂''y''₂

so we need to quickly determine the numbers ''x''₁''y''₁, ''x''₁''y''₂ + ''x''₂''y''₁ and ''x''₂''y''₂. The heart of Karatsuba's method lies in the observation that this can be done with only three rather than four multiplications:

# compute ''x''₁''y''₁, call the result ''A''

# compute ''x''₂''y''₂, call the result ''B''

# compute (''x''₁ + ''x''₂)(''y''₁ + ''y''₂), call the result ''C''

# compute ''C'' - ''A'' - ''B''; this number is equal to ''x''₁''y''₂ + ''x''₂''y''₁.

To compute these three products of ''m''-digit numbers, we can employ the same trick again, effectively using [[recursion]]. Once the numbers are computed, we need to add them together, which takes about ''n'' operations.

==Complexity==

If ''T''(''n'') denotes the time it takes to multiply two ''n''-digit numbers with Karatsuba's method, then we can write

:''T''(''n'') = 3 ''T''(''n''/2) + ''cn'' + ''d''

for some constants ''c'' and ''d'', and this [[recurrence relation]] can be solved using the [[master theorem]], giving a time complexity of Θ(''n''^ln(3)/ln(2)). 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 slower than long multiplication for small values of ''n''; typical implementations therefore switch to long multiplication if ''n'' is below some threshold.

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://www.swox.com/gmp/manual/Karatsuba-Multiplication.html][http://ozark.hendrix.edu/~burch/proj/karat/comment1.html] Karatsuba is surpassed by the asymptotically faster [[Schönhage-Strassen algorithm]] around 2^33,000.

==An Objective Caml implementation==