Karatsuba 乘法

執行 大數 的乘法，可以使用比通常的蠻力“長乘法”技術更少（很多）操作的方法。正如 Karatsuba (Karatsuba 和 Ofman 1962) 發現的那樣，兩個 -位 數字的乘法 可以透過小於 的 位複雜度 來完成，使用 以下形式 的恆等式

(1)

遞迴地進行下去，則得到 位複雜度 ，其中 (Borwein et al. 1989)。已知的最佳界限是 步，對於 (Schönhage 和 Strassen 1971, Knuth 1998)。然而，這個 演算法 難以實現，但是基於 快速傅立葉變換 的程式很容易實現，並且給出了 位複雜度 (Brigham 1974, Borodin 和 Munro 1975, Borwein et al. 1989, Knuth 1998)。

作為一個具體的例子，考慮在基數 中，兩個都只有兩位“數字”長的數字的乘法，

			(2)
			(3)

那麼它們的乘積是

			(4)
			(5)
			(6)

與其評估各個數字的乘積，現在寫成

			(7)
			(8)
			(9)

關鍵項是 ，它可以展開、重新分組，並用 表示為

(10)

然而，由於 和 ，立即得出

			(11)
			(12)
			(13)

因此， 的三個“數字”已使用三次乘法而不是四次乘法進行評估。該技術可以推廣到多位數字，但權衡是需要更多的加法和減法。

現在考慮四位“數字”的數字

(14)

它可以寫成以基數 表示的兩位“數字”的數字，

(15)

新基數中的“數字”現在是

			(16)
			(17)

並且 Karatsuba 演算法可以應用於這種形式的 和 。因此，Karatsuba 演算法不限於乘以兩位數，而更一般地將兩個數字的乘法表示為大小減半的數字的乘法。演算法透過遞迴應用於較小的所需子產品所獲得的漸近速度是 (Knuth 1998)。

當此技術遞迴應用於多位數字時，在遞迴中會達到一個點，此時加法和減法的開銷使得使用通常的 乘法 演算法來評估部分乘積更有效。因此，最有效的總體方法依賴於 Karatsuba 和傳統乘法的組合。