卡拉楚巴乘法（Karatsuba multiplication）
/ kah-rah-TSOO-bah /
你手算兩個大數相乘的方式——把一個數的每位數乘上另一個數的每位數再相加——對 n 位數需要約 n^2 次單位數乘法，這對密碼學中上千位的數慢得令人痛苦。卡拉楚巴於 1960 年發現的演算法，是第一個打敗它的方法，靠一個分治技巧以約 O(n^1.585) 相乘，用幾次便宜的加法換掉一次昂貴的乘法。
把每個 n 位數對半切：寫 x = a * 10^(n/2) + b 與 y = c * 10^(n/2) + d，其中 a,b,c,d 大致是 n/2 位的數。課本式乘積 x*y = ac * 10^n + (ad + bc) * 10^(n/2) + bd 需要四次半規模乘法（ac、ad、bc、bd），給出 T(n) = 4 T(n/2) + O(n) = O(n^2)——毫無收穫。卡拉楚巴的洞見是中間項 ad + bc 只需多一次乘法即可還原：算 p1 = ac、p2 = bd、p3 = (a+b)(c+d)；則 ad + bc = p3 - p1 - p2。這只是三次半規模乘法，所以 T(n) = 3 T(n/2) + O(n)。依主定理解得 O(n^(log2 3)) = O(n^1.585)。
卡拉楚巴是快速算術的入門，也完美說明遞迴呼叫的次數（即 a T(n/b) 中的 a）才是真正掌控速度的東西——從 4 次降到 3 次乘法就改變了指數。它被用在大整數函式庫處理中等大小的數，而把最大的數交給更快的 FFT 乘法。誠實的告誡是：額外的加法與遞迴開銷意味著卡拉楚巴只在超過某個交叉門檻（常是數百位）時才勝出；對小數，樸素的 O(n^2) 方法更快，所以函式庫會依大小在兩者間切換。
用 a=1,b=2,c=3,d=4 算 12 * 34：p1=ac=3、p2=bd=8、p3=(1+2)(3+4)=21、中間=21-3-8=10。結果 = 3*100 + 10*10 + 8 = 408。三次小乘法，而非四次。
以 (a+b)(c+d)-ac-bd 還原 ad+bc，把四次子乘法減為三次，使指數降到 log2(3)。
卡拉楚巴只在超過交叉大小（常為數百位）時才勝過課本式 O(n^2) 方法；對小數，它額外的加法反而使它更慢。