Content deleted Content added
Jorge Stolfi (talk | contribs) →Algorithm: Renamed the terms so that the lowest digit is 0 not 2; renamed X,Y to Z2,Z0; reworded analysis. |
|||
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.
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''<sub>1</sub>''B''<sup>''m''</sup> + ''x''<sub>2</sub>▼
:''y'' = ''y''<sub>1</sub>''B''<sup>''m''</sup> + ''y''<sub>2</sub>▼
::= ''x''<sub>1</sub>''y''<sub>1</sub>''B''<sup>2''m''</sup> + (''x''<sub>1</sub>''y''<sub>2</sub> + ''x''<sub>2</sub>''y''<sub>1</sub>)''B''<sup>''m''</sup> + ''x''<sub>2</sub>''y''<sub>2</sub>▼
:''xy'' = (''x''<sub>1</sub>''B''<sup>''m''</sup> + ''x''<sub>0</sub>)(''y''<sub>1</sub>''B''<sup>''m''</sup> + ''y''<sub>0</sub>)
::= ''z''<sub>2</sub> ''B''<sup>2''m''</sup> + ''z''<sub>1</sub> ''B''<sup>''m''</sup> + ''z''<sub>0</sub>
where
:Let ''X'' = ''x''<sub>1</sub>''y''<sub>1</sub>▼
:Let ''Y'' = ''x''<sub>2</sub>''y''<sub>2</sub>▼
:Let ''Z'' = (''x''<sub>1</sub> + ''x''<sub>2</sub>)(''y''<sub>1</sub> + ''y''<sub>2</sub>) - X - Y▼
:''z''<sub>0</sub> = ''x''<sub>0</sub>''y''<sub>0</sub>
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''<sub>1</sub>''y''<sub>1</sub> + ''x''<sub>1</sub>''y''<sub>2</sub> + ''x''<sub>2</sub>''y''<sub>1</sub> + ''x''<sub>2</sub>''y''<sub>2</sub>) - ''x''<sub>1</sub>''y''<sub>1</sub> - ''x''<sub>2</sub>''y''<sub>2</sub>▼
▲::= ''x''<sub>1</sub>''y''<sub>2</sub> + ''x''<sub>2</sub>''y''<sub>1</sub>
▲:
since
▲:
▲:
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<sup>32</sup> or ''B'' = 10<sup>9</sup>, 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<sup>''k''</sup>, for some integer ''k'', and the recursion stops only when ''n'' is 1, then the recursive Karatsuba algorithm performs at most 3<sup>''k''</sup> multiplications of 1-digit numbers; that is, ''n''<sup>''c''</sup> where ''c'' = log<sub>2</sub>3. When ''n'' is large, Karatsuba's algorithm is much faster than the grade school method, which requires ''n''<sup>2</sup> single-digit multiplications. If ''n'' = 2<sup>10</sup> = 1024, for example, it requires 3<sup>10</sup> 59,049 instead of (2<sup>10</sup>)<sup>2</sup> = 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==
|