動機
把兩個數各拆成高位和低位兩半,似乎需要四次規模更小的乘法:高位乘高位、高位乘低位、低位乘高位、低位乘低位。Karatsuba 的觀察是:只需多做一次乘法,就能得到兩個交叉乘積之和。遞歸乘積由四個減為三個,漸近指數因此改變。
這個算術恆等式本身很短,但嚴謹的複雜度證明必須考慮加法產生的進位,以及輸入長度不均勻的情形。我們分析一個刻意補零的實作,使其遞歸對每個數位長度都有定義,並且其運算次數不依賴於高位數字是否恰好為零。
定義
數位拆分與三個乘積
定義 1.6.1
(拆分與三個乘積)
固定基數 。考慮用至多 個 進制數位表示的非負整數 ,必要時在高位補零。當 大於某個固定的基礎情形閾值時,令 ,並寫成
其中 ,且 。定義
展開可得 ,因此
算法只遞歸地計算 ,再用加法、減法和數位移位恢復乘積。對於非負輸入,雖然 由減法得到,它仍然是非負的。有符號整數可以先對絕對值做乘法,再單獨恢復符號。
概念視角代數
二次多項式的三次求值
設 。則 , 是首項係數,。二次多項式由三個值決定,而 就是插值一步。乘積為 。
定理
定理 1.6.2
(三乘積恆等式的正確性)
對每個基數 以及按上述方式拆分的每一對非負輸入,三個遞歸乘積加上重組公式所得的結果等於普通的整數乘積 。
定理 1.6.3
(補零後的運算次數)
對下面的實作,固定基數下的數位運算次數為 。特別地,其上界在漸近意義上小於直接小學直式乘法的 數位運算上界。
最後一個命題比較的是固定基數數位運算模型中兩個指定的算法,它並不是對所有可能的乘法算法的下界。
證明思路或證明
正確性與補零
證明
(恆等式為何精確、遞歸為何終止)
展開 得到 。減去 和 後,剩下兩個交叉乘積。代入上面給出的重組恆等式,便還原出 的普通展開。
每一半至多有 位,但像 這樣的和可能因進位而需要 位。為了得到簡單統一的分析,我們把全部三個遞歸調用的參數都補零到 位,即使某個參數的有效位數更少。當規模至多為八時使用直接乘法。當 時,子問題規模 嚴格小於 ,所以遞歸會終止。
補零不改變被相乘的整數。重組過程使用移位 或 個數位,以及 位量的加法或減法,這些都可以在 次固定基數數位運算內完成。對補零後的規模作歸納,遞歸調用返回三個精確的乘積,因此該恆等式對每個輸入都證明了正確性。
證明透視
一個乘積同時編碼兩個交叉項
和的乘積包含全部四個兩兩乘積。去掉已經算出的低位乘低位與高位乘高位兩項後,恰好剩下兩個交叉項之和,而這正是重組所需要的全部資訊。
檢查數位長度與進位
每一半都小於 ,所以兩半之和小於 。因此,即使基數為二,它也能放進 個 進制數位中。把每個遞歸參數都補零到這一長度,就使三次調用保持統一。這是對表示長度的上界,並不斷言最高位非零。
中間乘積也只有 位。兩個至多 位的數之積小於 。在重組中,交叉項的值等於 ,且非負。從 中減去 和 ,可以借助普通的借位傳播,在線性多個數位上完成;只要以任意順序減去這兩個已知的非負乘積,就不需要出現負的中間值。
乘以 意味著把數位表示移位 個位置,或者等價地,把它對齊到輸出緩衝區中相應的偏移處。這不是再做一次與一般整數的遞歸乘法。把三個對齊後的貢獻相加,所需工作量與它們總表示長度成線性關係,進位按通常的數位加法算法處理。
比較兩個遞推式
直接的四乘積拆分在理想的等規模分析中具有 形式的遞推式,從而得到二次的數位運算量。Karatsuba 把分支因子降為三,於是子問題個數按 增長,而它們的規模大約按 縮小。第 層的線性工作量總和大致按 增長,在 的量級上由最深的幾層主導。
精確的取整遞推式並不是對每個整數 都恰好等於 。和的運算元可能有進位,補零後的規模為 。把規模平移三個單位,可以得到一個乾淨的折半不等式,同時避免把真實的實作替換成另一個理想化的遞推式。有限的基礎情形閾值隨後處理最小的那些情形,因為在這些情形中僅憑平移後的表達式並不能描述一個有意義的拆分。
取整規模下的上界
證明
(取整規模下的上界)
令 為補零算法數位工作量的上界。當 時,
對某個固定常數 成立,且規模至多為八時工作量為常數。其中加上的一用來計入可能的進位。定義平移後的規模 。若子問題規模為 ,則
因此,經過 層遞歸後,每個節點的規模至多為 。第 層至多有 個節點。令 ,則每條路徑在深度 處都已到達基礎閾值:其規模至多為八。非遞歸工作量的總和以下式的常數倍為界:
兩個幾何和都是 。事實上,,且 。常數規模的葉子也被同一個界所涵蓋。這就證明了上界,其中已包含取整與進位補零。
幾何和的估計
對 ,深度的取法滿足 。因此 至多是 的某個常數倍。類似地, 至多是下式的某個常數倍:
各層代價之和分別是公比為 與 的幾何級數,因此每個和都與其最後一項相差一個常數因子。對數的取整只改變這個常數。該證明同時計入了與規模成正比的重組工作量,以及每個遞歸節點的常數貢獻。
順序實作可以在每個遞歸乘積返回之後重用臨時儲存。沿著一條活動的遞歸路徑,補零後的規模按平移折半的界遞減,所以它們的規模之和為 。每個活動層使用常數個線性大小的緩衝區,於是除輸入和輸出之外,輔助數位儲存為 。若並行地執行三個遞歸調用,或保留額外的副本,則儲存的核算會改變,需要另行分析。
這一補零實作的下界
證明
(補零實作的匹配下界)
對 ,補零算法總是進行三次遞歸調用,每次的規模為 ,即使某些高位數字為零也是如此。對充分大的 ,令 。深度小於 的每個節點規模至少為 ,因此都不是基礎情形。遞歸樹在深度 處至少含有 個節點。
如果每個節點至少執行一次數位運算,這就給出了所指定的補零實作的一個匹配下界。補零的約定很重要:跳過零子乘積的實作,在某些特殊輸入上可以做更少的工作。上界依然成立,但這種針對具體輸入的下界論證就不能原封不動地適用了。
反例模式
輸入之和可能多出一位
在十進制中,兩個三位數,例如 與 ,其和 是四位數。若把每個和都當作三位輸入,而不設進位或補零規則,則遞歸規模的論證是不完整的。
指數比較的含義
因為 ,取以二為底的對數得 。因此,隨著 增大, 趨於零。這就是所述上界優於標準固定迴圈小學直式算法的二次運算次數的含義。對於小輸入,遞歸和臨時緩衝區可能帶來更大的常數代價,這也是實際實作要使用基礎情形的原因之一。
當兩個輸入都補零到 位且迴圈遍歷每一對數位時,標準的逐位方法要形成 個單獨的數位乘積。在固定基數下,每個這樣的數位乘積與進位更新的局部代價是有界的;累加移位後的各行,得到 次數位運算。這是對這一特定直接方法的分析,並不是整數乘法的普遍下界。
Karatsuba 基礎閾值取八,同樣是一種實作上的約定。只要閾值是固定的、足夠大的常數,並且當 超過閾值時 ,就會得到相同的漸近指數。閾值的取值只改變有限的常數,以及需要逐一檢驗的基礎情形,而不改變「三個分支與折半規模」之間的幾何比較。實際實作可以透過量度來選擇閾值,而證明只要求它是一個與輸入長度無關的固定常數。
輸出至多有 個 進制數位,因為 蘊含 。中間緩衝區可能因補零而含有多餘的前導零,但它們的長度仍與 成線性關係。這一關於輸出規模的觀察支持了上述線性重組與儲存的核算,但它本身並不能證明次二次的執行時間。
例題詳解
例題 1.6.4
(一個十進制乘法)
在 處拆分 與 :,,,。三個乘積為 ,,。因此 ,重組得到 。
例題 1.6.5
(為甚麼和的乘積有用)
對 ,兩個交叉乘積為 與 。不分別計算它們,而是使用 。恢復出的和為 。
例題 1.6.6
(奇數數位長度)
對 ,拆分使用 個低位數位,以及至多四個高位數位。低位部分與補零後的高位部分之和可能需要六位,所以每個遞歸調用都安全地補零到 位。這小於九,滿足在基礎閾值之上繼續推進的要求。
例題 1.6.7
(零輸入)
若 ,而 是任意非負輸入,該算術恆等式返回零。所指定的補零實作仍可能進行全部三次遞歸調用;其 運算次數描述的是這個實作,而不是偵測到零就提前退出的某種優化。
常見錯誤
常見錯誤
(只用一個交叉乘積)
中間係數是兩個交叉乘積的和。若只用其中一個交叉乘積代替,就會得到錯誤的乘法。三乘積技巧之所以有效,是因為和的乘積同時包含了兩個交叉項。
常見錯誤
(忽略運算元之和的進位)
進位會使和的運算元比一半多出一位。忽略這一點,可能得到對該實作並不成立的遞歸界。平移規模不等式明確地處理了這多出的一位。
常見錯誤
(把指數當成普遍的界)
是補零算法在所述模型下的運算次數。它並不是斷言別的算法不能更快地完成乘法,也不是斷言對任意精度的值,所有機器級運算的代價都相同。
總結
Karatsuba 乘法用三個乘積加線性重組取代了四個半規模乘積。對和的運算元補零處理了進位,而平移規模的遞歸樹論證控制了取整。對於所指定的始終遞歸的實作,所得的固定基數數位運算次數為 。
練習
快速檢查
(展開 。)
把和的乘積乘開再消項。
解答 · 答案
展開並消去後得到 。
快速檢查
(當 時,補零實作所用的遞歸參數規模是多少?)
先算 ,再加上進位的一位。
解答 · 答案
,所以遞歸參數規模為六位。
快速檢查
(為甚麼兩個 位輸入之和可能需要 位?)
想想把最大的數位相加。
解答 · 答案
它們相加可能在最高位產生進位。在十進制中, 就是一個例子。
快速檢查
(為甚麼本章的下界不能自動適用於遇到零運算元就立即返回的實作?)
下界的證明計數的是哪一個對象?
解答 · 答案
該證明計數的是一棵完整的、三分支且補零的遞歸樹。提前檢查零的做法對某些輸入可以去掉所有這些調用,因此被計數的那棵樹在該實作中不一定存在。