Karatsuba algorithm
Encyclopedia
The Karatsuba algorithm is a fast multiplication algorithm
. It was discovered by Anatolii Alexeevitch Karatsuba
in 1960 and published in 1962. It reduces the multiplication of two n-digit numbers to at most
single-digit multiplications in general (and exactly 
when n is a power of 2). It is therefore faster than the classical algorithm, which requires n2 single-digit products. If n = 210 = 1024, in particular, the exact counts are 310 = 59,049 and (210)2 = 1,048,576, respectively.
The Toom–Cook algorithm is a faster generalization of this algorithm. For sufficiently large n, another generalization, the Schönhage–Strassen algorithm, is even faster.
The Karatsuba algorithm was the first asymptotically fast multiplication algorithm.
in the big-O notation. In 1952, Andrey Kolmogorov
conjectured that the classical 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 (later it was called "divide and conquer") that multiplies two n-digit numbers in
elementary steps, thus disproving the conjecture. Kolmogorov was very upset about the discovery; he communicated it at the next meeting of the seminar, which was then terminated.
The method was published in 1962, in the Proceedings of the USSR Academy of Sciences
. The article had been written by Kolmogorov, possibly in collaboration with Yuri Ofman
, but listed "A. Karatsuba and Yu. Ofman" as the authors. Karatsuba only became aware of the paper when he received the reprints from the publisher.
Let x and y be represented as n-digit strings in some base
B. For any positive integer m less than n, one can split the two given numbers as follows
where x0 and y0 are less than Bm. The product is then
where
These formulae require four multiplications. Karatsuba observed that xy can be computed in only three multiplications, at the cost of a few extra additions:
since
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 = 2,147,483,648 or B = 109 = 1,000,000,000, and store each digit as a separate 32-bit binary word. Then the sums x1 + x0 and y1 + y0 will not need an extra carry-over digit (as in carry-save adder), and the Karatsuba recursion can be applied until the numbers are only 1 digit long.
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
gives the asymptotic
bound t(n) =
(nlog(3)/log(2)).
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 and context. As a rule of thumb, Karatsuba is usually faster when the multiplicands are longer than 320–640 bits.
Multiplication algorithm
A multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are in use...
. It was discovered by Anatolii Alexeevitch Karatsuba
Anatolii Alexeevitch Karatsuba
Anatolii Alexeevitch Karatsuba was a Russian mathematician, who authored the first fast multiplication method: the Karatsuba algorithm, a fast procedure for multiplying large numbers.- Studies and work :...
in 1960 and published in 1962. It reduces the multiplication of two n-digit numbers to at most
single-digit multiplications in general (and exactly when n is a power of 2). It is therefore faster than the classical algorithm, which requires n2 single-digit products. If n = 210 = 1024, in particular, the exact counts are 310 = 59,049 and (210)2 = 1,048,576, respectively.The Toom–Cook algorithm is a faster generalization of this algorithm. For sufficiently large n, another generalization, the Schönhage–Strassen algorithm, is even faster.
The Karatsuba algorithm was the first asymptotically fast multiplication algorithm.
History
The standard procedure for multiplication of two n-digit numbers requires a number of elementary operations proportional to n2, or in the big-O notation. In 1952, Andrey KolmogorovAndrey Kolmogorov
Andrey Nikolaevich Kolmogorov was a Soviet mathematician, preeminent in the 20th century, who advanced various scientific fields, among them probability theory, topology, intuitionistic logic, turbulence, classical mechanics and computational complexity.-Early life:Kolmogorov was born at Tambov...
conjectured that the classical algorithm was asymptotically optimal
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 worse than the best possible algorithm...
, meaning that any algorithm for that task would require
elementary operations.In 1960, Kolmogorov organized a seminar on mathematical problems in cybernetics
Cybernetics
Cybernetics is the interdisciplinary study of the structure of regulatory systems. Cybernetics is closely related to information theory, control theory and systems theory, at least in its first-order form...
at the Moscow State University
Moscow State University
Lomonosov Moscow State University , previously known as Lomonosov University or MSU , is the largest university in Russia. Founded in 1755, it also claims to be one of the oldest university in Russia and to have the tallest educational building in the world. Its current rector is Viktor Sadovnichiy...
, where he stated the
conjecture and other problems in the complexity of computationComputational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
. Within a week, Karatsuba, then a 23-year-old student, found an algorithm (later it was called "divide and conquer") that multiplies two n-digit numbers in
elementary steps, thus disproving the conjecture. Kolmogorov was very upset about the discovery; he communicated it at the next meeting of the seminar, which was then terminated.The method was published in 1962, in the Proceedings of the USSR Academy of Sciences
Proceedings of the USSR Academy of Sciences
The Proceedings of the USSR Academy of Sciences was a Soviet journal that was dedicated to publishing original, academic research papers in physics, mathematics, chemistry, geology, and biology...
. The article had been written by Kolmogorov, possibly in collaboration with Yuri Ofman
Yuri Petrovich Ofman
Yuri Petrovich Ofman is a Russian mathematician who works in computational complexity theory.He obtained his Doctorate from Moscow State University, where he was advised by Andrey Kolmogorov. He is the co-author with A. A...
, but listed "A. Karatsuba and Yu. Ofman" as the authors. Karatsuba only became aware of the paper when he received the reprints from the publisher.
The basic step
The basic step of Karatsuba's algorithm is a formula that allows us to compute the product of two large numbers x and y using three multiplications of smaller numbers, each with about half as many digits as x or y, plus some additions and digit shifts.Let x and y be represented as n-digit strings in some base
Radix
In mathematical numeral systems, the base or radix for the simplest case is the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.In any numeral...
B. For any positive integer m less than n, one can split the two given numbers as follows
- x = x1Bm + x0
- y = y1Bm + y0
where x0 and y0 are less than Bm. The product is then
- xy = (x1Bm + x0)(y1Bm + y0)
- = z2 B2m + z1 Bm + z0
where
- z2 = x1y1
- z1 = x1y0 + x0y1
- z0 = x0y0.
These formulae require four multiplications. Karatsuba observed that xy can be computed in only three multiplications, at the cost of a few extra additions:
- Let z2 = x1y1
- Let z0 = x0y0
- Let z1 = (x1 + x0)(y1 + y0) − z2 − z0
since
- z1 = x1y0 + x0y1 = (x1y1 + x1y0 + x0y1 + x0y0) − x1y1 − x0y0 = (x1 + x0)(y1 + y0) − x1y1 − x0y0.
Example
To compute the product of 1234 and 5678, choose B = 10 and m = 2. Then- 12 34 = 12 × 102 + 34
- 56 78 = 56 × 102 + 78
- z2 = 12 × 56 = 672
- z0 = 34 × 78 = 2652
- z1 = (12 + 34)(56 + 78) − z2 − z0 = 46 × 134 − 672 − 2652 = 2840
- result = z2 × 102×2 + z1 × 102 + z0 = 672 × 10000 + 2840 × 100 + 2652 = 7006652.
Recursive application
If n is four or more, the three multiplications in Karatsuba's basic step involve operands with less than n digits. Therefore, those products can be computed by recursiveRecursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
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 = 2,147,483,648 or B = 109 = 1,000,000,000, and store each digit as a separate 32-bit binary word. Then the sums x1 + x0 and y1 + y0 will not need an extra carry-over digit (as in carry-save adder), and the Karatsuba recursion can be applied until the numbers are only 1 digit long.
Efficiency 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
- t(n) = 3 t(
n/2
) + cn + d
for some constants c and d. For this recurrence relation
Recurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....
, the master theorem
Master theorem
In the analysis of algorithms, the master theorem provides a cookbook solution in asymptotic terms for recurrence relations of types that occur in the analysis of many divide and conquer algorithms...
gives the asymptotic
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
bound t(n) =
(nlog(3)/log(2)).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 and context. As a rule of thumb, Karatsuba is usually faster when the multiplicands are longer than 320–640 bits.
External links
- Karatsuba's Algorithm for Polynomial Multiplication
- Karatsuba multiplication Algorithm – Web Based Calculator (GPL)
- Bernstein, D. J., "Multidigit multiplication for mathematicians". Covers Karatsuba and many other multiplication algorithms.
- Karatsuba Multiplication on Fast Algorithms and the FEE
- Karatsuba using Sums of Squares Implementation