Content deleted Content added
m just fixed a typo Tags: Reverted Visual edit |
Grapesurgeon (talk | contribs) integer specify in lead |
||
| (13 intermediate revisions by 11 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 29 ⟶ 40:
==History==
The standard
In 1960, Kolmogorov organized a seminar on mathematical problems in [[cybernetics]] at the [[Moscow State University]], where he stated the <math>\Omega(n^2)\,\!</math> conjecture and other problems in the [[Computational complexity theory|complexity of computation]]. Within a week, Karatsuba, then a 23-year-old student, found an algorithm that multiplies two ''n''-digit numbers in <math>O(n^{\log_2 3})</math> elementary steps, thus disproving the conjecture. Kolmogorov was very excited about the discovery; he communicated it at the next meeting of the seminar, which was then terminated. Kolmogorov gave some lectures on the Karatsuba result at conferences all over the world (see, for example, "Proceedings of the International Congress of Mathematicians 1962", pp. 351–356, and also "6 Lectures delivered at the International Congress of Mathematicians in Stockholm, 1962") and published the method in 1962, in the [[Proceedings of the USSR Academy of Sciences]]. The article had been written by Kolmogorov and contained two results on multiplication, Karatsuba's algorithm and a separate result by [[Yuri Petrovich Ofman|Yuri Ofman]]; it listed "A. Karatsuba and Yu. Ofman" as the authors. Karatsuba only became aware of the paper when he received the reprints from the publisher.<ref name="kara1995"/>
Line 59 ⟶ 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 \\
&=
\end{align}
</math>
Thus only three multiplications are required for computing <math>z_0, z_1</math> and <math>z_2.</math>
===Example===
Line 82 ⟶ 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 98 ⟶ 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 104 ⟶ 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==
| |||