Karatsuba algorithm: Difference between revisions

Revision as of 20:49, 31 July 2008

Revision as of 06:08, 29 September 2008

Line 4:

The speed of this algorithm relies partly on the ability to do [[arithmetic shift|shift]]s faster than a standard multiply, with shifts typically taking [[linear time]] on a practical computer.

The basic step of Karatsuba's algorithm is a formula that allows us to compute the product of two large numbers ''x'' and ''y'' using three multiplications of smaller numbers, each with about half as many digits as ''x'' or ''y'', plus some additions and digit shifts.

We assume two ''n''-digit numbers ''x'' and ''y'', represented in [[radix|base]] ''B'' where ''B'' is a convenient value to shift with, like two in modern binary computers. Choosing a number ''m'' less than ''n'', we can write

Let ''x'' and ''y'' be represented as ''n''-digit strings in some [[radix|base]] ''B''. For any positive integer ''m'' less than ''n'', one can split the two given numbers as follows

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

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

where :''x''₂ and= ''yx''₂₁ are less than ''B''^''m''; it+ is easily seen that there is a unique representation. We now have''x''₀

:''xy'' = ''xy''₁''B''^''m'' + ''xy''₂₀

:''xy'' =where (''x''₁₀''B''^''m'' +and ''x''₂)(''y''₁₀ are less than ''B''^''m''. +The ''y''₂)product is then

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

:''xy'' = (''x''₁''B''^''m'' + ''x''₀)(''y''₁''B''^''m'' + ''y''₀)

The standard method is to multiply the four subproducts separately, then finally shift and add; this is O(n²). However, Karatsuba observed that we can compute ''xy'' in only three multiplications:

::= ''z''₂ ''B''^2''m'' + ''z''₁ ''B''^''m'' + ''z''₀

where

:Let ''X'' = ''x''₁''y''₁

:Let ''Y'' = ''x''₂''y''₂

:Let ''Z'' = (''x''₁ + ''x''₂)(''y''₁ + ''y''₂) - X - Y

:Let ''Yz''₂ = ''x''₂₁''y''₂₁

We note that

::''z''₁ = ''x''₁''y''₂₀ + ''x''₂₀''y''₁

:''z''₀ = ''x''₀''y''₀

These formulas require four multiplications. Karatsuba observed that we can compute ''xy'' in only three multiplications, at the cost of a few extra additions:

:''Z'' = (''x''₁''y''₁ + ''x''₁''y''₂ + ''x''₂''y''₁ + ''x''₂''y''₂) - ''x''₁''y''₁ - ''x''₂''y''₂

::= ''x''₁''y''₂ + ''x''₂''y''₁

:''y'' =Let ''yz''₁₂ = ''Bx''<supsub>''m''1</supsub> + ''y''₂₁

Thus ''xy'' = ''X'' ''B''^2m + ''Y'' + ''Z'' ''B''^m; we have cut down the number of multiplications from four to three.

:Let ''Xz''₀ = ''x''₁₀''y''₁₀

:''Z''Let = (''x''₁''yz''₁ += (''x''₁''y''₂ + ''x''₂₀)(''y''₁ + ''x''₂''y''₂₀) - ''x''z₁₂''y''₁ - ''x''z₂₀''y''₂

since

To compute these three products of ''m''-digit numbers, we can [[recursion|recursively]] employ Karatsuba multiplication again. The shifts, additions and subtractions take linear time respectively, and can be considered negligible.

::''z''₁ = (''x''₁''y''₁ + ''Bx''<supsub>1</sub>2''my''_{0</supsub> + (''x''₁₀''y''₂₁ + ''x''₂₀''y''₁₀) - ''Bx''<supsub>1}''my''<sub>1</supsub> +- ''x''₂₀''y''₂₀

Karatsuba multiplication works best when the two operands are of similar size; thus while one can theoretically choose ''m'' arbitrarily, the best time bound would be achieved by choosing ''m'' such that the subproducts are roughly equal, that is setting ''m'' to be about ''n''/2.

:Let ''Z'' := (''x''₁ + ''xy''₂₀)( + ''yx''₁₀ + ''y''₂₁) - X - Y

To compute these three products of ''m''-digit numbers, we can [[recursion|recursively]] employ Karatsuba multiplication again, until the numbers become so small that their product can be computed directly. One typically chooses ''B'' so that this condition is verified when the numbers are 1 digit each. In a computer with a full 32-bit by 32-bit [[multiplier circuit|multiplier]], for example, one could choose ''B'' = 2³² or ''B'' = 10⁹, and store each digit as a separate 32-bit binary word.

Karatsuba's basic step works for any base ''B'' and any ''m'', but the recursive algorithm is most efficient when, and ''m'' is equal to ''n''/2, rounded up. In particular, if ''n'' is 2^''k'', for some integer ''k'', and the recursion stops only when ''n'' is 1, then the recursive Karatsuba algorithm performs at most 3^''k'' multiplications of 1-digit numbers; that is, ''n''^''c'' where ''c'' = log₂3. When ''n'' is large, Karatsuba's algorithm is much faster than the grade school method, which requires ''n''² single-digit multiplications. If ''n'' = 2¹⁰ = 1024, for example, it requires 3¹⁰ 59,049 instead of (2¹⁰)² = 1,048,576 single-digit multiplies.

Since the additions, subtractions, and digit shifts (multiplications by powers of ''B'') in Karasuba's basic step take time proportional to ''n'', their cost of all becomes negligible as ''n'' increases.

==Example==