卡拉楚巴算法

Karatsuba算法/乘法、卡拉楚巴乘法/算法（），是一种快速乘法算法，由1960年提出并于1962年发表。  Knuth D.E.（1969）The art of computer programming. v.2. Addison-Wesley Publ.Co., 724 pp.它将两个位数字相乘所需的一位数乘法次数减少到了至多（如果是2的乘方，则正好为）。因此它比要次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（），卡拉楚巴算法需要次个位数乘法，而经典算法需要次。Toom–Cook算法是此算法更快速的泛型。对于充分大的，Schönhage-Strassen演算法甚至更快，算法的时间复杂度为。

值得一提的是，卡拉楚巴算法是第一个比小学二次乘法算法渐进快速的算法。

 算法 
卡拉楚巴算法主要是用于两个大数的乘法，极大提高了运算效率，相较于普通乘法降低了复杂度，并在其中运用了递归的思想。基本的原理和做法是将位数很多的两个大数和分成位数较少的数，每个数都是原来和位数的一半。这样处理之后，简化为做三次乘法，并附带少量的加法操作和移位操作。

 示例 
要計算12345和6789的乘積：
 12345 = 12 · 1000 + 345
  6789 =  6 · 1000 + 789

對只有三個數進行運算的乘法結果：
 z2 = 12 × 6 = 72
 z0 = 345 × 789 = 272205
 z1 = (12 + 345) × (6 + 789) − z2 − z0 = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

將三部分結果相加並相應地移位：
 結果 = z2 · (Bm)2 + z1 · (Bm)1 + z0 · (Bm)0, i.e.
 結果 = 72 · 10002 + 11538 · 1000 + 272205 = 83810205.

注意：中間第三次乘法運算的輸入域小於前兩次乘法的兩倍，其輸出域小於前兩次乘法的四倍，並且基數為1000的進位是根據前兩次乘法計算的，在計算這兩個減法時必須考慮。

 C代碼實現 
使用十六進制實現。
#include <math.h>
int karatsuba(int x, int y) {
    if (x < 16) or (y < 16) return x*y;
    /* calculates the size of the numbers */
    int m = (int)(log2(x+y) / 2),
        /* split the digit sequences about the middle */
        h1 = x >> m, l1 = x & m-1,
        h2 = y >> m, l2 = y & m-1;
    /* 3 calls made to numbers approximately half the size */
    int z0 = karatsuba(l1,l2),
        z1 = karatsuba((l1+h1),(l2+h2)),
        z2 = karatsuba(h1,h2);
    return (z2 << m*8)+(z1-z2-z0 << m*4)+(z0)
}

 Python代码实现 
使用十進制實現。
# Python 2 and 3
def karatsuba(num1, num2):
    num1Str, num2Str = str(num1), str(num2)

    if num1Str[0] == '-': return -karatsuba(-num1, num2)
    if num2Str[0] == '-': return -karatsuba(num1, -num2)

    if num1 < 10 or num2 < 10: return num1 * num2

    maxLength = max(len(num1Str), len(num2Str))
    num1Str = ''.join(list('0' * maxLength)[:-len(num1Str)] + list(num1Str))
    num2Str = ''.join(list('0' * maxLength)[:-len(num2Str)] + list(num2Str))

    splitPosition = maxLength // 2
    high1, low1 = int(num1Str[:-splitPosition]), int(num1Str[-splitPosition:])
    high2, low2 = int(num2Str[:-splitPosition]), int(num2Str[-splitPosition:])
    z0, z2 = karatsuba(low1, low2), karatsuba(high1, high2)
    z1 = karatsuba((low1 + high1), (low2 + high2))
    return z2 * 10 ** (2 * splitPosition) + (z1 - z2 - z0) * 10 ** (splitPosition) + z0

 参考文献 

 Karatsuba's Algorithm for Polynomial Multiplication

 Bernstein, D. J., "Multidigit multiplication for mathematicians". Covers Karatsuba and many other multiplication algorithms.

 外部鏈接 
 卡拉楚巴多項式乘法算法 

 Bernstein, D. J., "Multidigit multiplication for mathematicians ". Covers Karatsuba and many other multiplication algorithms.

Category:计算机算术算法
Category:乘法
Category:带有伪代码示例的条目