# Karatsuba算法

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

## 算法

### 基本步骤

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

## 实现

### 伪代码实现

```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)```

### Python代码实现

```#version 2.7.6
def karatsuba(num1, num2):
if (num1 < 10) or (num2 < 10):
return num1*num2
num1Str = str(num1)
num2Str = str(num2)

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

return (z2*10**(2*splitPosition)) + ((z1-z2-z0)*10**(splitPosition))+z0
```

## 参考文献

1. ^ A. Karatsuba and Yu. Ofman. Multiplication of Many-Digital Numbers by Automatic Computers. Proceedings of the USSR Academy of Sciences. 1962, 145: 293–294.
2. ^ A. A. Karatsuba. The Complexity of Computations (PDF). Proceedings of the Steklov Institute of Mathematics. 1995, 211: 169–183.
3. ^ Knuth D.E.（1969）The art of computer programming. v.2. Addison-Wesley Publ.Co., 724 pp.