卡拉楚巴算法

Karatsuba算法/乘法、卡拉楚巴乘法/算法（俄語：Алгоритм Карацубы），是一種快速乘法算法，由1960年阿納托利·阿列克謝耶維奇·卡拉楚巴（英語：Anatoly_Karatsuba）提出並於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}}$），卡拉楚巴算法需要${\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)}$。

洋紅色箭頭表示乘法，琥珀色表示加法，銀色表示減法，淺青色表示左移。A、B、C顯示了用於獲得中間值的遞歸。

值得一提的是，卡拉楚巴算法是第一個比小學二次乘法算法漸進快速的算法。

算法

卡拉楚巴算法主要是用於兩個大數的乘法，極大提高了運算效率，相較於普通乘法降低了複雜度，並在其中運用了遞歸的思想。基本的原理和做法是將位數很多的兩個大數${\displaystyle x}$和${\displaystyle y}$分成位數較少的數，每個數都是原來${\displaystyle x}$和${\displaystyle y}$位數的一半。這樣處理之後，簡化為做三次乘法，並附帶少量的加法操作和移位操作。

示例

要計算12345和6789的乘積：

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

對只有三個數進行運算的乘法結果：

z₂ = 12 × 6 = 72

z₀ = 345 × 789 = 272205

z₁ = (12 + 345) × (6 + 789) − z₂ − z₀ = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

將三部分結果相加並相應地移位：

結果 = z₂ · (B^m)² + z₁ · (B^m)¹ + z₀ · (B^m)⁰, i.e.

結果 = 72 · 1000² + 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