我們平時接觸的長乘法钥星，按位相乘闯两，是一種時間復(fù)雜度為 O(n ^ 2) 的算法笔诵。今天钟病，我們來介紹一種萧恕，時間復(fù)雜度為 O (n ^ log 3) 的大整數(shù)乘法(log 表示以 2 為底的對數(shù))。
介紹原理
karatsuba 算法要求乘數(shù)與被乘數(shù)要滿足以下幾個條件肠阱，第一票唆，乘數(shù)與被乘數(shù)的位數(shù)相同；第二屹徘，乘數(shù)與被乘數(shù)的位數(shù)應(yīng)為 2 次冪走趋，即為 2 ^ 2, 2 ^ 3, 2 ^ 4， 2 ^ n 等數(shù)值噪伊。
下面我們先來看幾個簡單的例子簿煌，并以此來了解 karatsuba 算法的使用方法氮唯。
兩位數(shù)相乘
我們設(shè)被乘數(shù) A = 85，乘數(shù) B = 41姨伟。下面來看我們的操作步驟：
將 A, B 一分為二惩琉，令 p = A 的前半部分 = 8，q = A 的后半部分 = 5 夺荒， r = B 的前半部分 = 4 瞒渠，s = B 的后半部分 = 1，n = 2技扼。通過簡單的數(shù)學(xué)運(yùn)算：
A * B = pq * rs = (p * 10 + q) * (r * 10 + s) = p * r * 10 ^ 2 + (p * s + q * r ) * 10 + q * s伍玖。
令 u = p * r，v = (p - q) * (s - r)剿吻，w = q * s窍箍。 所以 A * B = u * 10 ^ 2 + (u + v + w) * 10 + w。
換成數(shù)值求解的過程如下：
A * B = 85 * 41 = (8 * 10 + 5) * ( 4 * 10 + 1) = 8 * 4 * 10 * 10 + (8 * 1 + 5 * 4) * 10 + 5 * 1和橙。其中 u = 8 * 4 = 32仔燕，v = (8 - 5) (1 - 4) = -9，w = 5 * 1 = 5魔招。所以晰搀，A * B = 32 * 100 + (32 - 9 + 5) * 10 + 5 = 3485。與長乘法所得結(jié)果一致办斑。
四位數(shù)相乘
我們設(shè)被乘數(shù) A = 8537外恕，乘數(shù) B = 4123。下面來看我們的操作步驟：
將 A, B 一分為二乡翅，令 p = A 的前半部分 = 85鳞疲，q = A 的后半部分 = 37 ， r = B 的前半部分 = 41 蠕蚜，s = B 的后半部分 = 23尚洽，n = 4。
==> 其中靶累，u = 85 * 41, v = (85 - 37) * (23 - 41), w = 37 * 23腺毫。
==> A * B = 8537 * 4123 = u * 10 ^ 4 + (u + v + w) * 10 ^ 2 + w = 3485_0000 +34_7200 + 851 = 35198051。
在我們計算 u挣柬， v, w 的過程中又會涉及兩位數(shù)的乘法潮酒，我們繼續(xù)使用 Karatsuba 算法得出兩位數(shù)相乘的結(jié)果。
N 位數(shù)相乘
我們令 n 為 乘數(shù)與被乘數(shù)的位數(shù)邪蛔，令 p = A 的前半部分急黎，q = A 的后半部分， r = B 的前半部分 ，s = B 的后半部分勃教。
==> 其中淤击， u = p * r，v = (p - q) * (s - r)故源，w = q * s遭贸。 所以 A * B = u * 10 ^ n + (u + v + w) * 10 ^ (n / 2) + w。
而 u, v, w 則是兩個 n / 2 位的乘法運(yùn)算心软。我們繼續(xù)調(diào)用 Karatsuba 算法計算 u, v, w 的數(shù)值。接著著蛙，我們在計算 n / 2 乘法的過程中又會遇到 n / 4 位的乘法運(yùn)算……以此類推删铃，直到我們遇到兩個個位數(shù)的乘法，我們就直接返回這兩個個位數(shù)乘法的結(jié)果踏堡。層層返回猎唁，最終得到 N 位數(shù)的乘法結(jié)果。
代碼實(shí)現(xiàn)
代碼實(shí)現(xiàn)時顷蟆，需要將大整數(shù)先轉(zhuǎn)換為字符串诫隅，然后再截取相應(yīng)部分的數(shù)字，最后計算出最后結(jié)果帐偎。
# 關(guān)注微信公眾號：nim 編程
import math
import strutils
proc kara(a: int64, b: int64): int64 =
if a < 10 or b < 10:
return a * b
var a_str = $a
var b_str = $b
var a_len = a_str.len
var b_len = b_str.len
let real_len = float(max(a_len, b_len))
let max_len = 2 ^ int(ceil(log2(real_len)))
let mid = max_len shr 1
while a_len < max_len:
a_str = "0" & a_str
a_len += 1
while b_len < max_len:
b_str = "0" & b_str
b_len += 1
let p = parseInt(a_str[0 .. mid-1])
let q = parseInt(a_str[mid .. a_str.len-1])
let r = parseInt(b_str[0 .. mid-1])
let s = parseInt(b_str[mid .. b_str.len-1])
let u = kara(p, r)
let v = kara(q - p, s - r)
let w = kara(q, s)
return u * 10 ^ max_len + (u + w - v) * 10 ^ mid + w
輸出結(jié)果：
==> echo kara(123456, 9734) == 123456 * 9734
==> echo kara(1234233456756, 32459734) == 1234233456756 * 32459734
時間復(fù)雜度
我們平常使用的長乘法逐纬，是 O (n ^ 2) 的時間復(fù)雜度。比如兩個 N 位數(shù)相乘削樊，我們需要將每一位按規(guī)則相乘豁生，所以需要計算 N * N 次乘法。而使用 Karatsuba 算法每層需要計算三次乘法漫贞，兩次加法甸箱，以及若干次加法，每使用一次 karatsuba 算法迅脐，乘法規(guī)模就下降一半芍殖。所以，對于兩個 n = 2 ^ K 位數(shù)乘法運(yùn)算谴蔑，我們需要計算 3 ^ K 次乘法運(yùn)算豌骏。
而 K = log n(底數(shù)為 2)， 3 ^ K = 3 ^ log n = 2 ^ (log 3 * log n) = 2 ^ (log n * log 3) = n ^ log 3 （底數(shù)為 2）树碱。
