Karatsuba algorithm


Karatsuba algorithm

The Karatsuba multiplication algorithm, a technique for quickly multiplying large numbers, was discovered by Anatolii Alexeevich Karatsuba in 1960 and published in the joint paper with Yu. Ofman in 1962. It reduces the multiplication of two "n"-digit numbers to n^{log_23}approx n^{1.585} single-digit multiplications. This makes it faster than the classical algorithm, which requires "n"2 single-digit products. If "n" = 210 = 1024, for example, the counts are 310 = 59,049 and (210)2 = 1,048,576, respectively.

The Toom-Cook algorithm is a faster generalization of Karatsuba's. For sufficiently large "n", Karatsuba's algorithm is beaten by the Schönhage-Strassen algorithm.

The Karatsuba algorithm is a notable example of the divide and conquer paradigm, specifically of binary splitting.

Algorithm

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 "B". For any positive integer "m" less than "n", one can split the two given numbers as follows

:"x" = "x"1"B""m" + "x"0:"y" = "y"1"B""m" + "y"0

where "x"0 and "y"0 are less than "B""m". The product is then

:"xy" = ("x"1"B""m" + "x"0)("y"1"B""m" + "y"0)::= "z"2 "B"2"m" + "z"1 "B""m" + "z"0

where

:"z"2 = "x"1"y"1:"z"1 = "x"1"y"0 + "x"0"y"1:"z"0 = "x"0"y"0

These formulas require four multiplications. Karatsuba observed that we can compute "xy" in only three multiplications, at the cost of a few extra additions:

:Let "z"2 = "x"1"y"1:Let "z"0 = "x"0"y"0:Let "z"1 = ("x"1 + "x"0)("y"1 + "y"0) - "z2" - "z0"

since

:"z"1 = ("x"1"y"1 + "x"1"y"0 + "x"0"y"1 + "x"0"y"0) - "x"1"y"1 - "x"0"y"0 = "x"1"y"0 + "x"0"y"1

Example

Say we want to compute the product of 1234 and 5678. We choose "B" = 10 and "m" = 2. We have

:12 34 = 12 × 102 + 34:56 78 = 56 × 102 + 78:"z"2 = 12 × 56 = 672:"z"0 = 34 × 78 = 2652:"z"1 = (12 + 34)(56 + 78) - "z"2 - "z"0 = 46 × 134 - 672 - 2652 = 2840:result = "z"2 × 102×2 + "z"1 × 102 + "z"0 = 672 0000 + 2840 00 + 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 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 = 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 "x"1 + "x"0 and "y"1 + "y"0 will not need an extra carry-over digit (as in carry-save adder), and the 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, and "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" = 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 3^{ lceillog_2 n ceil} leq 3 n^{log_2 3}.

Since the additions, subtractions, and digit shifts (multiplications by powers of "B") in Karasuba's basic step take time proportional to "n", their cost of all 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 we can write

:"t"("n") = 3 "t"(lceil"n"/2 ceil) + "cn" + "d"

for some constants "c" and "d". For this recurrence relation, the master theorem gives the asymptotic bound "t"("n") = Θ("n"log(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 "n" is 10 or more [http://gmplib.org/manual/Karatsuba-Multiplication.html] [http://ozark.hendrix.edu/~burch/proj/karat/comment1.html]

References

* A. Karatsuba and Yu Ofman, "Multiplication of Many-Digital Numbers by Automatic Computers." Doklady Akad. Nauk SSSR, Vol. 145 (1962), pp. 293–294. Translation in Physics-Doklady, 7 (1963), pp. 595–596.
* Karacuba A. A. "Berechnungen und die Kompliziertheit von Beziehungen (German)." Elektron. Informationsverarb. Kybernetik, 11, 603–606 (1975).
* Karatsuba A. A. "The complexity of computations." Proc. Steklov Inst. Math., 211, 169–183 (1995); translation from Trudy Mat. Inst. Steklova, 211, 186–202 (1995).
* Knuth D.E. "The art of computer programming. v.2." Addison-Wesley Publ.Co., 724 pp., Reading (1969).
* [http://mathworld.wolfram.com/KaratsubaMultiplication.html Karatsuba Multiplication on MathWorld]
*Bernstein, D. J., " [http://cr.yp.to/papers/m3.pdf Multidigit multiplication for mathematicians] ". Covers Karatsuba and many other multiplication algorithms.
* [http://www.ccas.ru/personal/karatsuba/divcen.htm Karatsuba Multiplication on Fast Algorithms and the FEE]
* [http://www.saahiihii.com/storyPage.php?lang=ENU&country=DK&region=&orderBy=MostRecent&period=All&type=Business&businessNo=1354&memberID=enkya&page=DOCUMENT&section=EDUCATION&story=2&action=card Karatsuba Multiplication using Squares of a Difference]

External links

* [http://utilitymill.com/utility/Karatsuba_Multiplication Karatsuba multiplication Algorithm - Web Based Calculator (GPL)]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… …   Wikipedia

  • Cipolla's algorithm — In computational number theory, Cipolla s algorithm is a technique for solving a congruence of the form x2 = n, where , so n is the square of x, and where p is an odd prime. Here denotes the finite field with p elements; . Th …   Wikipedia

  • Williams' p + 1 algorithm — In computational number theory, Williams p + 1 algorithm is an integer factorization algorithm, one of the family of algebraic group factorisation algorithms. It was invented by Hugh C. Williams in 1982. It works well if the number N to be… …   Wikipedia

  • Cornacchia's algorithm — In computational number theory, Cornacchia s algorithm is an algorithm for solving the Diophantine equation x2 + dy2 = m, where and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia[1]. Contents 1 The algorithm …   Wikipedia

  • Divide and conquer algorithm — In computer science, divide and conquer (D C) is an important algorithm design paradigm based on multi branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub problems of the same (or… …   Wikipedia

  • 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 ,… …   Wikipedia

  • Toom–Cook multiplication — Toom–Cook, sometimes known as Toom 3, named after Andrei Toom and Stephen Cook, is a multiplication algorithm, a method of multiplying two large integers.Given two large integers, a and b , Toom–Cook splits up a and b into k smaller parts each of …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of Russian IT developers — This list of Russian IT developers includes the famous hardware engineers, computer scientists and programmers from the Russian Empire, the Soviet Union and the Russian Federation. See also the Category:Russian computer scientists and… …   Wikipedia

  • List of Russian mathematicians — Andrey Kolmogorov, a preeminent 20th century mathematician. This list of Russian mathematicians includes the famous mathematicians from the Russian Empire, the Soviet Union and the Russian Federation. This list is incomplete; you can help by …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.