Karatsuba algorithm

The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962.[1][2][3] 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. For example, the Karatsuba algorithm requires 310 = 59,049 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 210), whereas the classical algorithm requires (210)2 = 1,048,576.

The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. The Toom–Cook algorithm is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm 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 the big-O notation. 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 agitated about the discovery; he communicated it at the next meeting of the seminar, which was then terminated. Kolmogorov did some lectures on the Karatsuba result at the 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 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 step of Karatsuba's algorithm is 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.

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 one can calculate

which holds since


.

A more efficient implementation of Karatsuba multiplication can be set as [5] , where .

Example

To compute the product of 12345 and 6789, choose B = 10 and m = 3. Then we decompose the input operands using the resulting base (Bm = 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:

z2 = 12 × 6 = 72
z0 = 345 × 789 = 272205
z1 = (12 + 345) × (6 + 789) − z2z0 = 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 = z2 · B2m + z1 · Bm + z0, 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; but note also that this partial result z1 cannot be negative: to compute these subtractions, equivalent additions using complements to 10002 can also be used, keeping only the two least significant base-1000 digits for each number:

z1 = 283815 − 72 − 272205 = (283815 + 999928 + 727795) mod 10002 = 2011538 mod 10002 = 11538.

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 = 2,147,483,648, 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.

Asymmetric Karatsuba-like formulae

Karatsuba's original formula and other generalizations are themselves symmetric. For example, the following formula computes

with 6 multiplications in , where is the Galois field with two elements 0 and 1.

where and . We note that addition and subtraction are the same in fields of characteristic 2.

This formula is symmetrical, namely, it does not change if we exchange and in and .

Based on the second Generalized division algorithms ,[6] Fan et al. found the following asymmetric formula:

where and .

It is asymmetric because we can obtain the following new formula by exchanging and in and .

where and .

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

for some constants c and d. For this recurrence relation, the master theorem gives the asymptotic 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 and context. As a rule of thumb, Karatsuba is usually faster when the multiplicands are longer than 320–640 bits.[7]

Pseudocode

procedure karatsuba(num1, num2)
  if (num1 < 10) or (num2 < 10)
    return num1*num2
  /* calculates the size of the numbers */
  m = max(size_base10(num1), size_base10(num2))
  m2 = m/2
  /* split the digit sequences about the middle */
  high1, low1 = split_at(num1, m2)
  high2, low2 = split_at(num2, m2)
  /* 3 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^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)

References

  1. A. Karatsuba and Yu. Ofman (1962). "Multiplication of Many-Digital Numbers by Automatic Computers". Proceedings of the USSR Academy of Sciences. 145: 293–294. Translation in the academic journal Physics-Doklady, 7 (1963), pp. 595–596
  2. 1 2 A. A. Karatsuba (1995). "The Complexity of Computations" (PDF). Proceedings of the Steklov Institute of Mathematics. 211: 169–183. 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, Longman Green, London, 1864; page 125.
  5. Torbjörn Granlund and the GMP development team, The GNU Multiple Precision Arithmetic Library Manual, version 6.0.0, Free Software Foundation, Inc., March 2014.
  6. Haining Fan, Ming Gu, Jiaguang Sun, Kwok-Yan Lam,"Obtaining More Karatsuba-Like Formulae over the Binary Field", IET Information security Vol. 6 No. 1 pp. 14-19, 2012.

External links

This article is issued from Wikipedia - version of the 12/4/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.