The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It is a divide-and-conquer algorithm 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 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.

History
The standard procedure for multiplication of two n-digit numbers requires a number of elementary 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 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  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. 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 (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) − 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 like 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 .

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.

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.

Computer arithmetic algorithms
Multiplication
Articles with example pseudocode
Divide-and-conquer algorithms
카라추바 알고리즘은 소련의 수학자 아나톨리 알렉세예비치 카라추바가 1960년에 발견하고 1962년에 공개한, 큰 수에 대한 효과적인 곱셈 알고리즘이다.

이 방법은 두 n자리 수의 곱셈을 최대 (n이 2의 거듭제곱일 때는 정확하게 와 일치한다)개의 한 자리 곱셈으로 줄인다. 그러므로 이 방법은 n2개의 한 자리 곱셈을 해야하는 고전적인 곱셈 방법보다 빠르다. 만약 n = 210 = 1024 라면, 고전적인 방법에서는 (210)2 = 1,048,576 회의 한 자리 곱셈이 필요하지만, 이 방법으로는 310 = 59,049 회의 한 자리 곱셈만이 필요하다.

톰-쿡 곱셈법은 카라추바 알고리즘의 일반적인 형태이다. 충분히 큰 n에 대해 카라추바 알고리즘의 복잡도는 쇤하게-슈트라센 알고리즘보다 크다.

카라추바 알고리즘은 분할 정복 알고리즘의 좋은 예이다.

역사 
기본적으로 두 n자리 수의 곱셈은 n2에 비례하는 (점근 표기법으로는 )횟수의 기초 연산이 필요하다. 1952년 안드레이 콜모고로프는 고전적인 알고리즘이 의 연산 횟수로 점근적으로 최적화 될 수 있을 것이라고 추측했다.

1960년 가을, 콜모고로프는 모스크바 대학교에서 사이버네틱스에 관한 수학 문제들에 대한 세미나를 열었다. 그곳에서  추측과 다른 계산 복잡도 이론에 대한 문제들을 언급했다. 그 후 1주 만에 23살 학생 카라추바가 두 n자리수의 곱셈을 회의 기초 연산을 통해 행할 수 있는 분할 정복 알고리즘을 발견함으로써, 그 추측을 반증하였다. 콜모고로프는 그 발견에 매우 당황했다. 그는 마지막이 될 다음 세미나에서 이것을 알렸다.

이 방법은 1962년 소비에트 연방 과학 학회(Доклады Академии наук СССР)에 발표되었다. 그 논문은 콜모고로프가 유리 오프만과 협력하여 썼지만, 카라추바와 오프만이 저자로 올라갔다. 카라추바는 발표자로부터 사본을 받고 그 사실을 알게 되었다.

알고리즘

기본 단계 
카라추바 알고리즘의 기본 단계는 큰 두 수 x와 y의 곱을 자릿수가 x, y의 절반인 수들의 곱 3번과 덧셈과 시프트 연산을 이용해 계산하는 것이다.

x와 y를 B진법의 n자리수라고 하자. n보다 작은 양수 m에 대해 다음과 같이 x, y를 쪼갤 수 있다.

x = x1Bm + x0
y = y1Bm + y0

(단, x0과 y0는 Bm보다 작다.)

z2 = x1y1
z1 = x1y0 + x0y1
z0 = x0y0

라고 할 때, x와 y의 곱은
xy = (x1Bm + x0)(y1Bm + y0)
= z2 B2m + z1 Bm + z0

이 식은 4번의 곱셈을 해야한다. 카라추바는 덧셈을 몇 번 함으로써, xy를 3번의 곱셈을 통해 구할 수 있다는 걸 알았다.

z2 = x1y1 라 하자.
z0 = x0y0 라 하자.

z1 = (x1y1 + x1y0 + x0y1 + x0y0) - x1y1 - x0y0 = x1y0 + x0y1
이므로

z1 = (x1 + x0)(y1 + y0) − z2 − z0 라 할 수 있다.

예 
B = 10 이라하고, m = 2 라 하자. 1234와 5678의 곱을 구하고 싶으면,

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
결과 = z2 × 102×2 + z1 × 102 + z0 = 672 × 10000 + 2840 × 100 + 2652 = 7006652

재귀적 활용 
만약 n이 4 이상이면, 카라추바 알고리즘 기본 단계를 통해 n보다 작은 자리의 수에 대한 곱셈 3번을 하게 된다. 그러므로 재귀 호출을 통해 그 곱을 계산할 수 있다. 재귀 호출은 곱하는 수가 단번에 계산될 정도로 작아질 때까지 적용할 수 있다.

예를 들어 32비트끼리 곱하는 곱셈기에서 B = 231 = 2,147,483,648 or B = 109 = 1,000,000,000를 선택하고 각 자리를 독립된 32비트 단위로 저장할 수 있다. 그러면 x1 + x0와 y1 + y0에 여분의 자리올림 비트가 필요없고, 카라추바 재귀는 숫자가 한 자리가 될 때까지 반복가능하다.

효율성 분석 
카라추바 알고리즘 기본단계는 모든 B와 m에 대해 작동하지만, m이 n/2일 때 가장 효율적이다. 특히 양의 정수 k에 대해 n이 2k이고, 재귀가 n이 1일 때 끝난다면, 한 자리 곱셈의 횟수는 3k이 된다(nc에서 c = log23가 되므로).

카라추바 알고리즘 기본단계의 덧셈, 뺄셈, 시프트 연산(B의 거듭제곱으로 곱하는 것)은 n에 비례하는 시간이 걸리므로, 그 비용의 비중은 n이 증가함에 따라 무시할 정도로 줄어든다. 더 정확하게 t(n)이 두 n자리수의 곱셈에 필요한 기초연산의 총 횟수라고 할 때 다음과 같다.

t(n) = 3 t(n/2) + cn + d

(c와 d는 적당한 상수)
이런 재귀적 관계를 마스터 정리를 통해 풀면, 점근 표기법으로 t(n) = (nlog(3)/log(2))이라는 것을 알 수 있다.

충분히 큰 n에 대해, 카라추바 알고리즘은 고전적인 곱셈법보다 적은 횟수의 시프트 연산과 한 자리 곱셈을 행한다. 하지만 작은 n에 대하여는 추가적인 덧셈과 시프트 연산 때문에 고전적인 곱셈법보다 속도가 느려진다. 그 경계는 컴퓨터의 플랫폼에 따라 달라진다. 대략적으로 곱하는 수가 2320 ≈ 2 이상일 때 카라추바 알고리즘이 더 빠르다.

참조 

 Karacuba A. A. Berechnungen und die Kompliziertheit von Beziehungen (German). Elektron. Informationsverarb. Kybernetik, 11, 603–606 (1975).

외부 링크 

 카라추바 곱셈 알고리즘 - 웹 기반 계산기 (GPL)
 MathWorld의 카라추바 알고리즘
 Bernstein, D. J., "수학자를 위한 여러 자리 수의 곱셈법". 카라추바 알고리즘을 비롯한 여러 곱셈 알고리즘.
 "중국식 곱셈법" - 카라추바 알고리즘의 실용적인 활용 사례.

컴퓨터 산술 알고리즘
곱셈