Karatsuba算法/乘法、卡拉楚巴乘法/算法（），是一种快速乘法算法，由1960年提出并于1962年发表。它将两个n位数字相乘所需的一位数乘法次数减少到了至多3 n^{\log_23}\approx 3 n^{1.585}（如果n是2的乘方，则正好为n^{\log_23}）。因此它比要n^2次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（n = 1024 = 2^{10}），卡拉楚巴算法需要3^{10} = 59049次个位数乘法，而经典算法需要(2^{10})^2 = 1048576次。Toom–Cook算法是此算法更快速的泛型。对于充分大的n (n \gg 1)，Schönhage-Strassen演算法甚至更快，算法的时间复杂度为O(n\log n\log \log n)。

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

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

示例
要計算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
int karatsuba(int x, int y) {
if (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

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

参考文献

[http://www.cs.pitt.edu/~kirk/cs1501/animations/Karatsuba.html Karatsuba's Algorithm for Polynomial Multiplication]

Bernstein, D. J., "[http://cr.yp.to/papers/m3.pdf Multidigit multiplication for mathematicians]". Covers Karatsuba and many other multiplication algorithms.

外部鏈接

[http://www.cs.pitt.edu/~kirk/cs1501/animations/Karatsuba.html 卡拉楚巴多項式乘法算法]

Bernstein, D. J., "[http://cr.yp.to/papers/m3.pdf Multidigit multiplication for mathematicians] ". Covers Karatsuba and many other multiplication algorithms.

卡拉楚巴算法

Python 2 and 3

评论 (0)