![Karatsuba_multiplication](https://upload.wikimedia.org/wikipedia/commons/0/03/Karatsuba_multiplication.svg)
The Karatsuba algorithm is a fast
multiplication algorithm
A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the de ...
. It was discovered by
Anatoly Karatsuba
Anatoly Alexeyevich Karatsuba (his first name often spelled Anatolii) (russian: Анато́лий Алексе́евич Карацу́ба; Grozny, Soviet Union, 31 January 1937 – Moscow, Russia, 28 September 2008) was a Russian mathematician ...
in 1960 and published in 1962.
[
][
][
Knuth D.E. (1969) '']The Art of Computer Programming
''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of compu ...
. v.2.'' Addison-Wesley Publ.Co., 724 pp.
It is a
divide-and-conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...
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
single-digit multiplications. It is therefore
asymptotically faster than the
traditional
A tradition is a belief or behavior (folk custom) passed down within a group or society with symbolic meaning or special significance with origins in the past. A component of cultural expressions and folklore, common examples include holidays or ...
algorithm, which performs
single-digit products. For example, the traditional algorithm requires (2
10)
2 = 1,048,576 single-digit multiplications to multiply two 1024-digit numbers (''n'' = 1024 = 2
10), whereas the Karatsuba algorithm requires 3
10 = 59,049 thus being ~17.758 times faster.
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
The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971.A. Schönhage and V. Strassen,Schnelle Multiplikation großer Zahlen, ''C ...
(1971) is even faster, for sufficiently large ''n''.
History
The standard procedure for multiplication of two ''n''-digit numbers requires a number of elementary operations proportional to
, or
in
big-O notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Land ...
.
Andrey Kolmogorov
Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...
conjectured that the traditional algorithm was ''
asymptotically optimal
In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly en ...
,'' meaning that any algorithm for that task would require
elementary operations.
In 1960, Kolmogorov organized a seminar on mathematical problems in
cybernetics
Cybernetics is a wide-ranging field concerned with circular causality, such as feedback, in regulatory and purposive systems. Cybernetics is named after an example of circular causal feedback, that of steering a ship, where the helmsperson m ...
at the
Moscow State University
M. V. Lomonosov Moscow State University (MSU; russian: Московский государственный университет имени М. В. Ломоносова) is a public research university in Moscow, Russia and the most prestigious ...
, 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 ''Proceedings of the USSR Academy of Sciences'' (russian: Доклады Академии Наук СССР, ''Doklady Akademii Nauk SSSR'' (''DAN SSSR''), french: Comptes Rendus de l'Académie des Sciences de l'URSS) was a Soviet journal that ...
. The article had been written by Kolmogorov and contained two 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.
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
The imaginary unit or unit imaginary number () is a solution to the quadratic equation x^2+1=0. Although there is no real number with this property, can be used to extend the real numbers to what are called complex numbers, using addition an ...
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
Charles Babbage (; 26 December 1791 – 18 October 1871) was an English polymath. A mathematician, philosopher, inventor and mechanical engineer, Babbage originated the concept of a digital programmable computer.
Babbage is considered ...
. Karatsuba observed that
can be computed in only three multiplications, at the cost of a few extra additions. With
and
as before one can observe that
:
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 (''B''
''m'' = ''1000''), as:
: 12345 = 12 · ''1000'' + 345
: 6789 = 6 · ''1000'' + 789
Only three multiplications, which operate on smaller integers, are used to compute three partial results:
: ''z''
2 = 12 × 6 = 72
: ''z''
0 = 345 × 789 = 272205
: ''z''
1 = (12 + 345) × (6 + 789) − ''z''
2 − ''z''
0 = 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'' like for the input operands):
: result = ''z''
2 · (''B''
''m'')
''2'' + ''z''
1 · (''B''
''m'')
''1'' + ''z''
0 · (''B''
''m'')
''0'', i.e.
: result = 72 · ''1000''
2 + 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
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
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'' = 2
31 and store each digit as a separate 32-bit binary word. Then the sums ''x''
1 + ''x''
0 and ''y''
1 + ''y''
0 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
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
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 2
''k'', for some integer ''k'', and the recursion stops only when ''n'' is 1, then the number of single-digit multiplications is 3
''k'', which is ''n''
''c'' where ''c'' = log
23.
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
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
, the
master theorem for divide-and-conquer recurrences gives the
asymptotic
In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...
bound
.
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. The point of positive return depends on the
computer platform
A computing platform or digital platform is an environment in which a piece of software is executed. It may be the hardware or the operating system (OS), even a web browser and associated application programming interfaces, or other underlying s ...
and context. As a rule of thumb, Karatsuba's method is usually faster when the multiplicands are longer than 320–640 bits.
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.
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
External links
Karatsuba's Algorithm for Polynomial Multiplication*
* Bernstein, D. J.,
Multidigit multiplication for mathematicians. Covers Karatsuba and many other multiplication algorithms.
{{Number-theoretic algorithms
Computer arithmetic algorithms
Multiplication
Articles with example pseudocode
Divide-and-conquer algorithms