顯而易見的做法是平方級
你早就會把兩個 n 位數相乘了：小時候學的那套直式乘法。一個數的每位數要乘上另一個數的每位數，所以你做了約 n^2 次的單位數乘法，再把它們加起來。那就是顯而易見的演算法，而它老老實實是平方級的——位數加倍，工作量就變四倍。幾十年來沒人認真相信能做得更好；乘法感覺像位數本身一樣不可化簡。本篇的驚奇在於：那個顯而易見的成本「並非」真正的成本，而填平這道差距的，是分治法加上一個巧妙的轉折。
我們先用最天真的方式試試分治，純粹是想看它幫不上忙。把每個 n 位數切成高半段和低半段：x = a * 10^(n/2) + b，y = c * 10^(n/2) + d，其中 a、b、c、d 各長 n/2 位。把乘積展開，你得到 x * y = a*c * 10^n + (a*d + b*c) * 10^(n/2) + b*d。那些乘上十的次方的位移與加法都很便宜，是 O(n) 的工作。但看看那四個乘積 a*c、a*d、b*c、b*d——每一個都是兩個半大數的相乘，所以我們有四次遞迴呼叫，輸入規模各為 n/2。
這給出遞迴關係式 T(n) = 4 T(n/2) + O(n)。把它解開——用遞迴樹或主定理——答案是 Theta(n^2)。我們分了、遞迴了、便宜地合了，結果得到「跟課本乘法一模一樣的平方成本」。分與治在這裡什麼都沒換到，因為工作堆在葉子上：四個分支、每個把規模減半，光是樹的最底層就已經花掉 Theta(n^2)。要真正獲勝，我們必須對付「四」這個數字。
卡拉楚巴：三次乘法取代四次
這就是開啟這一切的招數，出自卡拉楚巴在 1960 年的成果。我們需要三個量：a*c、b*d，以及中間項 a*d + b*c。天真的計畫分別算 a*d 和 b*c，光為了中間項就花掉兩次乘法。卡拉楚巴的洞見是：我們從不需要單獨的 a*d 和 b*c——我們只需要它們的「和」。而那個和有一條代數捷徑。算出單一乘積 (a + b) * (c + d)。展開後得到 a*c + a*d + b*c + b*d。我們已經從另外兩個乘積拿到了 a*c 和 b*d，所以把它們減掉，剩下的正好就是 a*d + b*c。
p1 = a * c
p2 = b * d
p3 = (a + b) * (c + d)
middle = p3 - p1 - p2 # equals a*d + b*c, with NO extra multiply
x*y = p1 * 10^n + middle * 10^(n/2) + p2
naive split: T(n) = 4 T(n/2) + O(n) -> Theta(n^2)
Karatsuba: T(n) = 3 T(n/2) + O(n) -> Theta(n^1.585)現在數一數乘法次數：p1、p2、p3——只有三次對 size-n/2 輸入的遞迴呼叫，不是四次。多出來的加法和減法全是 O(n)，被吸進合的成本裡。於是遞迴關係式變成 T(n) = 3 T(n/2) + O(n)。主定理把葉子的工作對上基準指數 n^(以 b 為底 a 的對數)，這裡是 n^(以 2 為底 3 的對數)。因為現在是三個分支而非四個，那個臨界指數就從以 2 為底 4 的對數 = 2，掉到以 2 為底 3 的對數，約為 1.585。整個演算法跑在 Theta(n^1.585)——嚴格快過平方級，而且是免費的，靠花一次便宜的加法去閃過一次昂貴的乘法。
史特拉森：同一個構想用在矩陣上
現在把完全一樣的遊戲往上玩一個維度，用矩陣。把兩個 n×n 矩陣相乘的顯而易見做法照定義來：結果的 n^2 個元素裡，每一個都是長度為 n 的內積，總共 Theta(n^3) 次純量乘法。試試天真的分治：把每個矩陣切成四個 n/2×n/2 的區塊。依照通常的規則，兩個區塊矩陣的乘積需要八次區塊乘積（四個結果區塊裡，每一個都是兩個半大矩陣乘積之和）。那是 T(n) = 8 T(n/2) + O(n^2)，臨界指數為以 2 為底 8 的對數 = 3——又回到 Theta(n^3)。跟之前是同一個故事：盲目切成八塊什麼都換不到。
1969 年，史特拉森從矩陣這頂帽子裡掏出了卡拉楚巴那隻兔子。他把輸入區塊組成七個精心挑選的和與差，把它們相乘得到七個乘積而非八個，再用更多加法把它們合起來，就還原出答案的全部四個區塊。那七個乘積 P1 到 P7 看起來毫無神奇之處——像 (A11 + A22)(B11 + B22) 這樣的組合——但它們的加法與減法恰好重組出四個結果區塊。和卡拉楚巴一樣，省下的功夫來自從不單獨計算那八個天真乘積，而只算出能據以重建答案的七個組合。
七次遞迴乘法取代八次，給出 T(n) = 7 T(n/2) + O(n^2)。合的工作現在是 O(n^2)——n/2×n/2 區塊的加法比之前多——但矩陣加法相對於乘法很便宜，而 O(n^2) 並不主宰。主定理直接讀出臨界指數以 2 為底 7 的對數，約 2.807，所以史特拉森跑在大約 Theta(n^2.807)。這跟卡拉楚巴是同一根槓桿：把分支數減一，主宰葉子的那個指數就剛好降到足以打敗那個顯而易見的演算法。
誠實的附帶細則
若讓你以為史特拉森和卡拉楚巴就是更好、你應該永遠用它們，那會是不誠實的。指數確實改善了，但隱藏常數變糟了：史特拉森的七個乘積伴隨著大約十八次區塊加法，每層的記帳遠比乾淨俐落的八乘積天真切分要多。大O符號藏的正是這類常數。因為漸進優勢只在 n^2.807 有意義地拉到 n^3 之下時才顯現，交叉點只發生在夠大的 n——小矩陣用顯而易見的方式相乘更快，這正是為什麼真實的函式庫一旦區塊縮到某個門檻以下就改回課本乘法。
而這兩個結果都不是路的終點。卡拉楚巴的 1.585 是 n^2 那道牆上的第一道裂縫；後來用更多碎片的方法（Toom-Cook）把指數推得更低，而快速傅立葉轉換把大整數與多項式乘法一路帶到約 Theta(n log n)——那是個不同且更深的構想，在本階下一篇指南裡涵蓋。至於矩陣，史特拉森的 2.807 已被一再打破，更繁複的演算法把指數一點一點推向 2；那些是常數巨大的理論里程碑，實務上很少真的拿來跑。卡拉楚巴與史特拉森之所以重要，不是因為它們是定論，而是因為它們教會我們那根槓桿：數一數遞迴乘法的次數，然後拿掉一次。
那根槓桿，一個動作
退一步看，兩個故事裡的食譜是同一份。把問題切成 b 倍小的碎片；注意到天真做法需要 a 次遞迴乘法；找一條代數恆等式，用 a − 1 次乘法加上一些額外的便宜加法重新算出同一答案；在合步驟裡為那些加法買單。因為由葉子主宰的成本由主定理的指數「以 b 為底 a 的對數」設定，把 a 降一，就把指數降下來——而較小的指數對大輸入終究會獲勝。
- 天真切分：a 次遞迴乘法，遞迴關係式 T(n) = a T(n/b) + O(n^k)，指數為以 b 為底 a 的對數。
- 找一條恆等式，用 a − 1 次乘法、外加只是 O(n^k) 的加法，算出同樣的輸出。
- 新的遞迴關係式 T(n) = (a−1) T(n/b) + O(n^k)，帶著較小的指數「以 b 為底 (a−1) 的對數」。
- 卡拉楚巴：4 → 3 給出 n^1.585；史特拉森：8 → 7 給出 n^2.807。同一根槓桿，兩個舞台。
這就是值得帶著走的一課。那個顯而易見的演算法不是自然律；它只是你最先想到的東西。當工作堆在遞迴的葉子上時，獲勝之道很少是合得更巧妙，而幾乎總是遞迴得更少次——是找到那條隱藏的代數恆等式，讓 a − 1 個乘積頂替 a 個。卡拉楚巴與史特拉森是兩個最乾淨的示範，證明多做一點點算術去跳過單一次遞迴呼叫，就能扳動一個指數。