|
==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''<sub>1</sub> ''W''<sup>''m''</sup> + ''x''<sub>2</sub>
: ''y'' = ''y''<sub>1</sub> ''W''<sup>''m''</sup> + ''y''<sub>2</sub>
with ''m''-digit numbers ''x''<sub>1</sub>, ''x''<sub>2</sub>, ''y''<sub>1</sub> and ''y''<sub>2</sub>. The product is given by
: ''xy'' = ''x''<sub>1</sub>''y''<sub>1</sub> ''W''<sup>2''m''</sup> + (''x''<sub>1</sub>''y''<sub>2</sub> + ''x''<sub>2</sub>''y''<sub>1</sub>) ''W''<sup>''m''</sup> + ''x''<sub>2</sub>''y''<sub>2</sub>
so we need to quickly determine the numbers ''x''<sub>1</sub>''y''<sub>1</sub>, ''x''<sub>1</sub>''y''<sub>2</sub> + ''x''<sub>2</sub>''y''<sub>1</sub> and ''x''<sub>2</sub>''y''<sub>2</sub>. The heart of Karatsuba's method lies in the observation that this can be done with only three rather than four multiplications:
# compute ''x''<sub>1</sub>''y''<sub>1</sub>, call the result ''A''
# compute ''x''<sub>2</sub>''y''<sub>2</sub>, call the result ''B''
# compute (''x''<sub>1</sub> + ''x''<sub>2</sub>)(''y''<sub>1</sub> + ''y''<sub>2</sub>), call the result ''C''
# compute ''C'' - ''A'' - ''B''; this number is equal to ''x''<sub>1</sub>''y''<sub>2</sub> + ''x''<sub>2</sub>''y''<sub>1</sub>.
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==
| 