Content deleted Content added
→Implementation: I believe z1 was incorrect in the pseudo code, so I fixed it. Tag: Reverted |
Grapesurgeon (talk | contribs) integer specify in lead |
||
| (22 intermediate revisions by 18 users not shown) | |||
Line 1:
{{short description|Algorithm for integer multiplication}}
{{Infobox algorithm
[[File:Karatsuba_multiplication.svg|thumb|300px|Karatsuba multiplication of az+b and cz+d (boxed), and 1234 and 567. Magenta arrows denote multiplication, amber denotes addition, silver denotes subtraction and light cyan denotes left shift. (A), (B) and (C) show recursion used to obtain intermediate values.]]▼
|class = [[Multiplication algorithm]]
The '''Karatsuba algorithm''' is a fast [[multiplication algorithm]]. It was discovered by [[Anatoly Karatsuba]] in 1960 and published in 1962.<ref name="kara1962">▼
|image = <!-- filename only, no "File:" or "Image:" prefix, and no enclosing [[brackets]] -->
|caption =
|data =
|time = <!-- Worst time big-O notation -->
|best-time =
|average-time =
|space = <!-- Worst-case space complexity; auxiliary space
(excluding input) if not specified -->
}}
▲[[File:Karatsuba_multiplication.svg|thumb|300px|Karatsuba multiplication of az+b and cz+d (boxed), and 1234 and 567 with z=100. Magenta arrows denote multiplication, amber denotes addition, silver denotes subtraction and
▲The '''Karatsuba algorithm''' is a fast [[multiplication algorithm]] for [[Integer|integers]]. It was discovered by [[Anatoly Karatsuba]] in 1960 and published in 1962.<ref name="kara1962">
{{cite journal
| author = A. Karatsuba and Yu. Ofman
Line 9 ⟶ 20:
| year = 1962
| pages = 293–294
| url = https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=26729&option_lang=eng
| postscript = . Translation in the academic journal ''[[Physics-Doklady]]'', '''7''' (1963), pp. 595–596}}
</ref><ref name="kara1995">
Line 22 ⟶ 34:
</ref><ref name="knuthV2">
Knuth D.E. (1969) ''[[The Art of Computer Programming]]. v.2.'' Addison-Wesley Publ.Co., 724 pp.
</ref> It is a [[divide-and-conquer algorithm]] that reduces the multiplication of two ''n''-digit numbers to three multiplications of ''n''/2-digit numbers and, by repeating this reduction, to at most <math> n^{\log_23}\approx n^{1.58}</math> single-digit multiplications. It is therefore [[Asymptotic complexity|asymptotically faster]] than the [[long multiplication|traditional]] algorithm, which performs <math>n^2</math> single-digit products
The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm.
Line 58 ⟶ 70:
:<math>z_0 = x_0 y_0.</math>
These formulae require four multiplications and were known to [[Charles Babbage]].<ref>Charles Babbage, Chapter VIII – Of the Analytical Engine, Larger Numbers Treated, [https://archive.org/details/bub_gb_Fa1JAAAAMAAJ/page/n142 <!-- pg=125 --> Passages from the Life of a Philosopher], Longman Green, London, 1864; page 125.</ref> Karatsuba observed that <math>xy</math> can be computed in only three multiplications, at the cost of a few extra additions. With <math>z_0</math> and <math>z_2</math> as before and <math>z_3=(x_1 + x_0) (y_1 + y_0),</math> one can observe that
:<math>
\begin{align}
z_1 &= x_1 y_0 + x_0 y_1 \\
&= (x_1 + x_0) (y_0 + y_1) - x_1 y_1 - x_0 y_0 \\
&= z_3 - z_2 - z_0. \\
\end{align}
</math>
Thus only three multiplications are required for computing <math>z_0, z_1</math> and <math>z_2.</math>
===Example===
Line 72 ⟶ 91:
: ''z''<sub>1</sub> = ('''12''' + '''345''') '''×''' ('''6''' + '''789''') − ''z''<sub>2</sub> − ''z''<sub>0</sub> = 357 '''×''' 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538
We get the result by just adding these three partial results, shifted accordingly (and then taking carries into account by decomposing these three inputs in base ''1000''
: result = ''z''<sub>2</sub> · (''B''<sup>''m''</sup>)<sup>''2''</sup> + ''z''<sub>1</sub> · (''B''<sup>''m''</sup>)<sup>''1''</sup> + ''z''<sub>0</sub> · (''B''<sup>''m''</sup>)<sup>''0''</sup>, i.e.
: result = 72 · ''1000''<sup>2</sup> + 11538 · ''1000'' + 272205 = '''83810205'''.
Line 88 ⟶ 107:
Since one can extend any inputs with zero digits until their length is a power of two, it follows that the number of elementary multiplications, for any ''n'', is at most <math>3^{ \lceil\log_2 n \rceil} \leq 3 n^{\log_2 3}\,\!</math>.
Since the additions, subtractions, and digit shifts (multiplications by powers of ''B'') in Karatsuba's basic step take time proportional to ''n'', their cost becomes negligible as ''n'' increases. More precisely, if ''
:<math>T(n) = 3 T(\lceil n/2\rceil) + cn + d</math>
Line 94 ⟶ 113:
for some constants ''c'' and ''d''. For this [[recurrence relation]], the [[master theorem (analysis of algorithms)|master theorem for divide-and-conquer recurrences]] gives the [[big O notation|asymptotic]] bound <math>T(n) = \Theta(n^{\log_2 3})\,\!</math>.
It follows that, for sufficiently large ''n'', Karatsuba's algorithm will perform fewer shifts and single-digit additions than longhand multiplication, even though its basic step uses more additions and shifts than the straightforward formula. For small values of ''n'', however, the extra shift and add operations may make it run slower than the longhand method.
==Implementation==
Line 102 ⟶ 121:
The second argument of the split_at function specifies the number of digits to extract from the ''right'': for example, split_at("12345", 3) will extract the 3 final digits, giving: high="12", low="345".
<syntaxhighlight lang="
function karatsuba
if (num1 < 10
return num1 × num2 /* fall back to traditional multiplication */
/* Calculates the size of the numbers. */
m =
m2 = floor
/* m2 = ceil (m / 2) will also work */
/* Split the digit sequences in the middle. */
high1, low1 = split_at
high2, low2 = split_at
/* 3 recursive calls made to numbers approximately half the size. */
z0 = karatsuba
z1 = karatsuba
z2 = karatsuba
return (z2 × 10 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0
| |||