10/08/2024, 13:09 Karatsuba algorithm - Wikipedia
Karatsuba algorithm
The Karatsuba algorithm is a fast multiplication algorithm.
Karatsuba algorithm
It was discovered by Anatoly Karatsuba in 1960 and published
in 1962.[1][2][3] It is a divide-and-conquer algorithm that Class Multiplication algorithm
reduces the multiplication of two n-digit numbers
to three multiplications of n/2-digit numbers and,
by repeating this reduction, to at most
single-digit multiplications. It is
therefore asymptotically faster than the traditional
algorithm, which performs single-digit products.
The Karatsuba algorithm was the first
multiplication algorithm asymptotically faster than
the quadratic "grade school" algorithm. The Toom–
Cook algorithm (1963) is a faster generalization of
Karatsuba's method, and the Schönhage–Strassen
algorithm (1971) is even faster, for sufficiently large
n.
Karatsuba multiplication of az+b and cz+d
History (boxed), and 1234 and 567 with z=100. Magenta
arrows denote multiplication, amber denotes
addition, silver denotes subtraction and cyan
The standard procedure for multiplication of two n-
denotes left shift. (A), (B) and (C) show recursion
digit numbers requires a number of elementary
with z=10 to obtain intermediate values.
operations proportional to , or in big-O
notation. Andrey Kolmogorov conjectured that the
traditional algorithm was asymptotically optimal, meaning that any algorithm for that task would
require elementary operations.
In 1960, Kolmogorov organized a seminar on mathematical problems in cybernetics at the Moscow
State University, where he stated the conjecture and other problems in the complexity of
computation. Within a week, Karatsuba, then a 23-year-old student, found an algorithm that
multiplies two n-digit numbers in 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
https://en.wikipedia.org/wiki/Karatsuba_algorithm 1/5
10/08/2024, 13:09 Karatsuba algorithm - Wikipedia
results on multiplication, Karatsuba's algorithm and a separate result by 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.[2]
Algorithm
Basic step
The basic principle of Karatsuba's algorithm is divide-and-conquer, using a formula that allows
one to compute the product of two large numbers and using three multiplications of smaller
numbers, each with about half as many digits as or , plus some additions and digit shifts. This
basic step is, in fact, a generalization of a similar complex multiplication algorithm, where the
imaginary unit i is replaced by a power of the base.
Let and be represented as -digit strings in some base . For any positive integer less than
, one can write the two given numbers as
where and are less than . The product is then
where
These formulae require four multiplications and were known to Charles Babbage.[4] Karatsuba
observed that can be computed in only three multiplications, at the cost of a few extra
additions. With and as before and one can observe that
Thus only three multiplications are required for computing and
Example
To compute the product of 12345 and 6789, where B = 10, choose m = 3. We use m right shifts for
decomposing the input operands using the resulting base (Bm = 1000), as:
12345 = 12 · 1000 + 345
6789 = 6 · 1000 + 789
https://en.wikipedia.org/wiki/Karatsuba_algorithm 2/5
10/08/2024, 13:09 Karatsuba algorithm - Wikipedia
Only three multiplications, which operate on smaller integers, are used to compute three partial
results:
z2 = 12 × 6 = 72
z0 = 345 × 789 = 272205
z1 = (12 + 345) × (6 + 789) − z2 − z0 = 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 as for the input operands):
result = z2 · (Bm)2 + z1 · (Bm)1 + z0 · (Bm)0, i.e.
result = 72 · 10002 + 11538 · 1000 + 272205 = 83810205.
Note that the intermediate third multiplication operates on an input domain which is less than two
times larger than for the two first multiplications, its output domain is less than four times larger,
and base-1000 carries computed from the first two multiplications must be taken into account
when computing these two subtractions.
Recursive application
If n is four or more, the three multiplications in Karatsuba's basic step involve operands with fewer
than n digits. Therefore, those products can be computed by recursive calls of the Karatsuba
algorithm. The recursion can be applied until the numbers are so small that they can (or must) be
computed directly.
In a computer with a full 32-bit by 32-bit multiplier, for example, one could choose B = 231 and
store each digit as a separate 32-bit binary word. Then the sums x1 + x0 and y1 + y0 will not need
an extra binary word for storing the carry-over digit (as in carry-save adder), and the Karatsuba
recursion can be applied until the numbers to multiply are only one digit long.
Time complexity analysis
Karatsuba's basic step works for any base B and any m, but the recursive algorithm is most
efficient when m is equal to n/2, rounded up. In particular, if n is 2k, for some integer k, and the
recursion stops only when n is 1, then the number of single-digit multiplications is 3k, which is nc
where c = log23.
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 .
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 T(n) denotes the total number of elementary operations that the algorithm performs when
multiplying two n-digit numbers, then
for some constants c and d. For this recurrence relation, the master theorem for divide-and-
conquer recurrences gives the asymptotic bound .
https://en.wikipedia.org/wiki/Karatsuba_algorithm 3/5
10/08/2024, 13:09 Karatsuba algorithm - Wikipedia
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
Here is the pseudocode for this algorithm, using numbers represented in base ten. For the binary
representation of integers, it suffices to replace everywhere 10 by 2.[5]
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".
function karatsuba(num1, num2)
if (num1 < 10 or num2 < 10)
return num1 × num2 /* fall back to traditional multiplication */
/* Calculates the size of the numbers. */
m = max(size_base10(num1), size_base10(num2))
m2 = floor(m / 2)
/* m2 = ceil (m / 2) will also work */
/* Split the digit sequences in the middle. */
high1, low1 = split_at(num1, m2)
high2, low2 = split_at(num2, m2)
/* 3 recursive calls made to numbers approximately half the size. */
z0 = karatsuba(low1, low2)
z1 = karatsuba(low1 + high1, low2 + high2)
z2 = karatsuba(high1, high2)
return (z2 × 10 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0
An issue that occurs when implementation is that the above computation of and
for may result in overflow (will produce a result in the range ),
which require a multiplier having one extra bit. This can be avoided by noting that
This computation of and will produce a result in the range of
. This method may produce negative numbers, which require one extra bit to
encode signedness, and would still require one extra bit for the multiplier. However, one way to
avoid this is to record the sign and then use the absolute value of and to
perform an unsigned multiplication, after which the result may be negated when both signs
originally differed. Another advantage is that even though may be negative,
the final computation of only involves additions.
References
1. A. Karatsuba and Yu. Ofman (1962). "Multiplication of Many-Digital Numbers by Automatic
Computers" (https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=267
29&option_lang=eng). Proceedings of the USSR Academy of Sciences. 145: 293–294.
Translation in the academic journal Physics-Doklady, 7 (1963), pp. 595–596
2. A. A. Karatsuba (1995). "The Complexity of Computations" (http://www.ccas.ru/personal/karats
uba/divcen.pdf) (PDF). Proceedings of the Steklov Institute of Mathematics. 211: 169–183.
https://en.wikipedia.org/wiki/Karatsuba_algorithm 4/5
10/08/2024, 13:09 Karatsuba algorithm - Wikipedia
Translation from Trudy Mat. Inst. Steklova, 211, 186–202 (1995)
3. Knuth D.E. (1969) The Art of Computer Programming. v.2. Addison-Wesley Publ.Co., 724 pp.
4. Charles Babbage, Chapter VIII – Of the Analytical Engine, Larger Numbers Treated, Passages
from the Life of a Philosopher (https://archive.org/details/bub_gb_Fa1JAAAAMAAJ/page/n14
2), Longman Green, London, 1864; page 125.
5. Weiss, Mark A. (2005). Data Structures and Algorithm Analysis in C++. Addison-Wesley.
p. 480. ISBN 0321375319.
External links
Karatsuba's Algorithm for Polynomial Multiplication (http://www.cs.pitt.edu/~kirk/cs1501/animati
ons/Karatsuba.html)
Weisstein, Eric W. "Karatsuba Multiplication" (https://mathworld.wolfram.com/KaratsubaMultipli
cation.html). MathWorld.
Bernstein, D. J., "Multidigit multiplication for mathematicians (http://cr.yp.to/papers/m3.pdf)".
Covers Karatsuba and many other multiplication algorithms.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Karatsuba_algorithm&oldid=1235911416"
https://en.wikipedia.org/wiki/Karatsuba_algorithm 5/5
