為甚麼要計算除法次數
歐幾里得(Euclid)算法通過反覆帶餘除法計算最大公因數。證明結果正確只是分析的一半:我們還想知道,對於給定輸入,算法要做多少次除法。答案具有精確的極值形式:若 且算法做了 次除法,則 和 至少分別是兩個特定的相鄰斐波那契(Fibonacci)數;這對斐波那契數恰好達到下界。
原因在於餘數鏈的結構:每一步中,一個餘數至少是後面兩個餘數之和。斐波那契遞推則對應每一步都取等號的情況。建立這一點後,斐波那契數的增長就給出除法次數的對數上界。
還要區分兩種成本:除法次數是對數級,不意味著位元運算次數也是對數級。一次大整數除法本身可能很昂貴。以下始終把這兩種度量分開。
定義
定義 1.2.1
(任意整數的最大公因數)
對於不全為零的整數 , 是同時整除兩者的最大正整數。每個整數都整除 ,因此 沒有最大的公因數。我們約定 。在此約定下,對任意整數 都有 ,並且 。
定義 1.2.2
(算法與除法次數)
給定整數 ,先取絕對值;若此時 ,就交換兩者,使 。取絕對值和交換都不算除法。
若 ,返回 ,除法次數為零。特別地, 返回 ,算法絕不會除以零。
若 ,令 、。對 ,只要 就進行一次除法:
設首次出現零餘數的下標為 ,即 。除法次數是 ,其中包括最後一次餘數為零的除法;算法輸出 。
定義 1.2.3
(斐波那契數)
定義 、,且對 ,。序列開始為
下面要注意重複的值 。序列從 起非遞減,從 起嚴格遞增。
正確性、終止性與貝祖係數
定理 1.2.4
(歐幾里得不變量)
若 ,則 。
證明
(相鄰數對的公因數)
若 同時整除 和 ,它就整除 。
反過來,若 整除 和 ,它也整除 。
因此兩對數的公因數集合完全相同,從而最大公因數相同;若兩數均為零,也依約定同為 。
餘數滿足 。非負整數不可能無限嚴格下降,所以至多經過 次除法就出現零餘數,算法必定終止。沿餘數鏈應用不變量,得到
定理 1.2.5
(擴展歐幾里得不變量)
令 、、、,並定義
則每個 都滿足 。特別地,。
證明
(對下標歸納)
和 時由初值直接成立。
假設等式對 和 成立,則
對於帶符號的輸入,先對 應用結論,若開始時交換過輸入,先把係數交換回來,再將每個係數乘以對應原輸入的符號;零輸入的貢獻為零。
斐波那契下界
定理 1.2.6
(除法次數的下界)
設 ,算法進行 次除法,則
證明
(從最後一個非零餘數向前推)
我們證明對 ,有 。其中 和 分別給出兩項結論。
情形 。 須證明 和 。首先 ;其次由 得 。這裏直接用到了 。
情形 :初始步驟 。 最後一個非零餘數為正,因此 。
情形 :初始步驟 。 最後一次除法為 。由於 , 是更早的除法以 為除數所得的餘數,故 ,從而 。於是 。
情形 :歸納步驟。 取 ,令 ,則 。在除法 中,: 時這是假設 , 時來自餘數嚴格遞減。因此 ,而
證明透視
下界為何由下往上推,以及 $a$ 大於 $b$ 在哪裏用到
證明從餘數鏈的底部讀起。除法 只要 ,便給出 ,這就是不等式形式的斐波那契遞推;所以兩個相鄰餘數的下界給出它們上方那個餘數的下界。這也是歸納需要兩個初始情形的原因:最後一個非零餘數至少為 ,而它上方的餘數至少為 ,因為 迫使 。
假設 只在最頂端的除法用到:它給出 ( 時則直接給出 )。較低位置的商自動至少為 ,因為餘數嚴格遞減。用同一條鏈分析等號:所有不等式同時取等號,恰好當 、 且其餘的商都等於 ,此時這條鏈重現相鄰的斐波那契數。
不能去掉 。若 ,算法只做一次除法 ,故 。下界 仍成立,但在 上 失敗。證明中失效的正是 。
定理 1.2.7
(相鄰斐波那契輸入達到極值)
對每個 ,輸入 恰好需要 次除法。除最後一次的商為 外,其餘商均為 。
證明
(注意序列底部)
商為 1 的除法。 對 ,有
嚴格不等式成立是因為 ,所以這確是合法的帶餘除法。
餘數鏈。 從 開始,數對依次變為 。這裏對 各做一次除法,共 次。
最後一次除法。 雖然 ,餘數 並不小於除數 ,所以它不是帶餘除法。正確的一步是 。
合計。 共 次除法。
令 ,輸入 需要 次除法。因此定理中的下界對每個 都能達到; 時由 達到。向前推的證明中,每個不等式同時取等號,當且僅當 、 且此前各商均為 。
概念視角代數
把餘數鏈寫成矩陣乘積
每次除法可寫成 ,其中 的兩行是 與 。把 次除法連起來,得
各元素都是 的非負係數多項式,所以當 、 而其餘商都等於 時, 與 最小;這時兩行為 、 的矩陣的冪給出相鄰的斐波那契數。由於 ,把乘積求逆便得到貝祖(Bézout)係數。
除法次數的對數上界
定理 1.2.8
(增長界)
當 時,。令 ,則當 時,。
證明
(利用 歸納)
第一個界在下文關於 的練習中證明。對於第二個界,注意 是 的正根。初始情形是 和 。當 時,歸納得到
應用增長界。 若 且做了 次除法,則 。 時這是上述定理; 時 ,且 。因此
推導 形式。 因為 ,所以 ,從而
時 ,因此對每個 都有 。使用 使表達式在 時也有意義。 時恰有一次除法 ,與兩個上界均一致。
除法次數與位元複雜度
假設兩個輸入各至多有 位元。
除法次數。 ,故 。
一次除法的成本。 每次除法涉及的數至多有 位元。普通直式除法每次需 次位元運算。
總成本。 因而 是有效的簡單上界。這只是上界,更仔細的分析可以改進;這裏不追求改進,也不聲稱它是最優位元複雜度。
輸入大小不只是 。 只計算除法次數,且只依賴較小輸入。若 固定而 有 位,除法次數雖少,第一次除法仍須讀取並除一個 位元整數。位元成本不能僅用 的函數來界定。
例題
例題 1.2.9
( 與貝祖係數)
除法。
故 ,。
回代。 第二式給出 ;第一式給出 。代入得
核對。 ,,兩者之差為 。
擴展不變量。 商依次為 ,係數表給出 、、。 與回代一致;最後一對滿足 ,符合不變量。
斐波那契界。 時,定理要求 和 ,兩者都遠大於下界。
例題 1.2.10
(相鄰斐波那契輸入 )
,故 ,預測有 次除法:
共七次除法,最大公因數為 。六個商為 ,最後一個商為 。
時,定理要求 、,兩者都取等號。因此,沒有滿足 且 的數對需要七次除法。
例題 1.2.11
(相等輸入與初始交換)
相等。 對 ,唯一一次除法 給出 ,最大公因數為 。
交換。 對 ,規範化將輸入交換為 ,它需要 次除法,最大公因數為 。
另一種約定。 若不先交換,而立即執行 ,這一步以商 完成交換並額外計作一次除法,次數就是 。按本節約定,交換不計入除法,因此次數為 。
例題 1.2.12
(第一個商很大)
對 ,
故 。需要三次除法且滿足 的最小 是 ,由 達到。 離最壞情形很遠:第一個商 一步就消去了 的大部分。
較大的商使餘數下降較快;如相鄰斐波那契輸入的例題,商為 時下降最慢。
常見錯誤
反例模式
除法次數為對數級不代表位元成本為對數級
錯誤說法。 「算法做 次除法,因此運行時間是 。」
反駁。 取 ,令 是任意 位元整數。
除法次數少。 第一個餘數屬於 ,因此最多做三次除法; 增長時次數仍有界。
每一位都有影響。 翻轉 的第 位會使它改變 。這個變化不能被 整除,故會改變 。正確執行第一次除法因而必須依賴 的每一位。
結論。 位元成本至少與 成正比,而 。計數除法衡量的是算術步驟,不是位元運算量。
還有以下常見錯誤:
- 除以零。 的數對,包括 ,按約定立即返回。
- 斷言位元運算始終對輸入位數呈線性增長。 這裏在普通直式除法下證明的是 位元運算上界,並未聲稱更強結果。
常見錯誤
(漏掉最後一次除法)
有些作者不計最後一次零餘數除法,次數比這裏少一,斐波那契下標也會相應變化。必須先說明約定。
常見錯誤
(在 時套用 )
表明這一界需要 。
常見錯誤
(在斐波那契鏈末尾寫 )
餘數必須嚴格小於除數;正確的是 。
練習
快速檢查
(對 運行算法,計算除法次數,並求整數 使 。)
解答
除法。
故 ,最大公因數為 。
回代。 從 開始,由 得
再由 ,
核對。 ,故 、。
係數表核對。 為 , 為 ,最後一對 與回代一致。
定理核對。 時要求 和 ,兩者均成立。
快速檢查
(計算 的除法次數,並與下界定理比較。)
解答
除法。
因此 。
比較。 輸入是 ,故 ,極值定理預測 ,與計算一致。下界 和 均取等號。
快速檢查
(按本節約定,求 時 、 以及 的輸出和除法次數。)
解答
。 規範化將其交換為 。算法不做除法,返回 ;確有 。
。 算法不做除法,返回 。
。 算法返回 ,符合 的約定;不做除法,也不會嘗試除以零。
每種情形的貝祖等式都可直接寫出,例如 ,以及 。
快速檢查
(證明 總需一次除法。準確說明 的證明在哪裏失效,以及哪個界仍成立。)
解答
一次除法。 帶餘除法為 ,且 ,故 。
證明失效之處。 時,證明由 推出 ;當 時這一步不能使用,且 。對於相等的正輸入,、,因此 仍成立;真正失效的是上述 時推出 的步驟。
仍成立的界。 仍成立。當 時, 恰好成立,但這並非由該定理推出。
快速檢查
(對 ,其中 是 位元整數,給出除法次數的上界。解釋為何第一個商很大,以及為何位元成本不可能與 無關。)
解答
次數上界。 寫成 ,其中 。
- :共一次除法。
- :下一步是 ,共兩次。
- :後續是 和 ,共三次。
故 ,與 的界一致。
第一個商。 ;由於 ,這個商約有 位元。
位元成本。 如反例所示,餘數 依賴每一位;輸出 本身也須寫出約 位元。因此第一次除法至少需要與 成正比的位元運算。除法次數有界,位元成本仍隨 增長。
快速檢查
(證明 時 ,再對 推出 。)
解答
初始情形。 ,。
歸納步驟。 對 ,序列從下標 起非遞減,故 。應用 的歸納假設,得到
推論。 若 且做了 次除法,下界定理給出
取 得 ,即 。