動機
一個算法僅僅在若干例子上碰巧有效是不足夠的。它的證明必須說明:每次更新之後有哪些性質仍然成立,更新為何最終會停止,以及最終狀態為何回答了原先的問題。整數算法令這些要求變得具體。歐幾里得(Euclid)算法保持公因數以及線性組合證書;二進制冪運算則保持一個部分完成的冪的值。
定義
定義 4.1.1
(不變式與成本模型)
迴圈不變式是關於程式狀態的一個命題,它在第一次迭代之前成立,並且被每一次迭代所保持。終止度量是一個非負整數,每當再執行一次迭代時它都嚴格減小。部分正確性是指:只要計算終止,它便返回正確的答案;完全正確性則還包括終止性。算術運算次數把每一種指定的算術運算都算作一步。位元複雜度則計算對單個二進制位的運算次數,因此對不斷增大的整數所做的算術並不自動具有常數成本。
不變式與終止度量的作用不同。單有不變式,它在一個無限的計算過程中也可能一直成立。單有遞減的度量,可以證明計算會停止,卻不能說明其答案的意義。應當同時陳述兩者,然後利用停止條件取出所需的結果。
定理/命題
定理 4.1.2
(擴展歐幾里得算法返回一個證書)
對於整數 ,初始化 ,以及係數對 ,。當 時,令 ,並同時將各數對替換為
終止時,。共進行 次除法。
定理 4.1.3
(二進制冪運算)
給定 、 以及整數 ,初始化 。當 時,在每次迭代中寫 ,其中 ,並同時設
輸出為 。當 時,它至多使用 次模乘法,其中一次平方算作一次乘法。
證明思路
證明
(擴展歐幾里得算法:證書、最大公因數與終止)
在擴展歐幾里得算法中,證書不變式是對 有 。它在初始時成立;在同時更新之下,用一個等式減去 倍的另一個等式,恰好保持該不變式。一個數在更新之前同時整除兩個餘數,當且僅當它在更新之後同時整除兩個餘數。因此兩者的最大公因數始終保持為 。新的第二個餘數介乎 與舊的 之間,這就證明了終止性。結束時第一個餘數為正而第二個為零,於是該不變式給出了所宣稱的證書。
關於除法次數:每連續兩次除法,相關的正餘數至少縮小為原來的一半。若下一個餘數本身已不超過當前餘數的一半,這是顯然的;否則它們的商為一,而再下一個餘數是兩者之差,小於一半。經過 次除法之後,不再有正的餘數。這是一個除法次數,並不表示大整數的除法是常數時間。
證明透視
三個事實,三種分工
歐幾里得算法的證明結合了三個事實,各自負責一件事。證書等式 得以保持,是因為餘數列與兩列係數都經歷同一個線性更新 ;線性就是全部理由。最大公因數得以保持,是因為 與 有相同的公因數:前一對的公因數整除 ,後一對的公因數整除 。這兩點都不依賴 的選取,任何整數都可以。只有終止性用到 ,因為它給出 。退出條件使論證閉合:當 時,當前的 就是上一步為正的 ,而 ,所以被保持的最大公因數就是當前第一個餘數,被保持的等式則用 與 把它表示出來。
證明
(二進制冪運算:未完成冪的不變式)
在二進制冪運算中,不變式是 。對於 ,更新後的狀態滿足
模 約化把這一等式以同餘式的形式保持下來。非負的度量 嚴格遞減直至為零。此時不變式變為 。若 ,則不會發生任何迭代,正確的結果是 。否則, 的每一個二進制位對應一次迭代,每次迭代包含一次平方以及至多一次額外的乘法。
例題詳解
例題 4.1.4
(作為可驗證輸出的擴展歐幾里得算法)
對於 ,各次的商為 ,餘數為 。回代得到 。輸出可以獨立檢驗: 整除兩個輸入,並且是它們的整係數組合。任何公因數都必定整除該組合,這就證明了它是最大公因數。
例題 4.1.5
(由證書得到模逆元)
對於 與 ,等式 給出 。確實 。如果最大公因數大於一,同一算法則會證明逆元不可能存在。
例題 4.1.6
(按二進制讀取指數)
計算 ,其中 。狀態 依次為 、、、、。因此答案是 。每次更新都使用舊的 來同時計算累積器與平方。若在累積器中使用已經平方過的 ,所表示的便是另一個指數。
由所求答案設計不變式
不變式最有用之處,在於它把當前狀態與原先的輸入連繫起來。僅關於當前餘數的斷言,也許只能描述它們為正或遞減的次序,卻不能說明它們代表的是哪一對輸入的最大公因數。保持最大公因數的不變式提供了這種連繫。係數不變式則進一步加強了它:即使當前的餘數可能小得多,它仍保留一個以原先輸入表示的明確表達式。
最終的輸出同時需要這兩類資訊。一個正的整數組合並不自動是最大公因數,因為可能的組合有很多。一個公因數也不自動是最大的。歐幾里得算法對全部公因數的保持,加上最後的零餘數,確定了正確的值,而係數等式則提供了一個簡潔的證書。證明之所以行得通,是因為各次更新恰好在停止狀態下保持了所需的資訊。
對於二進制冪運算,人們容易說累積器始終等於「到目前為止」所求的答案。這個說法過於含糊,無法證明任何東西。累積器與剩餘冪的乘積,給出了一個把狀態與原先指數連繫起來的精確等式。一旦剩餘指數為零,未完成的因子便變為一,該陳述也就成為所要求的結論。不變式的形式正是為了使最後這一代入起決定作用而選定的。
兩個證明都遵循同一個四步模式。首先在初始狀態下核對不變式。其次證明一次迭代保持該不變式,並在每個更新的右側都使用舊值。然後把不變式與退出條件結合,確定輸出。最後給出一個嚴格遞減的非負度量。前三步建立部分正確性;第四步把它提升為完全正確性。
同時更新與實現次序
數學上的賦值記號常常掩蓋了需要保留舊值這一點。在歐幾里得更新中,新的第一個餘數是舊的第二個餘數,而新的第二個餘數同時用到兩個舊的餘數。如果在計算第二個餘數之前便覆蓋了第一個餘數,該表達式就不再是證明所假定的意思。同樣的問題分別適用於兩列係數。
直接的實現可以先把所有新值算入暫存變量,然後替換舊的狀態。另一種實現可以使用元組賦值,只要所用語言先計算右側才覆蓋左側。只要與數學上的同時更新一致,兩者都是正確的。重要的約定在於語義而不在於風格:下一個狀態必須是已經證明其不變式得以保持的那個狀態。
符號與零輸入也屬於輸入約定。定理是針對有序的正輸入陳述的,這樣每一步除法以及餘數遞減的論證都是顯然的。對於一般帶符號的輸入,先取絕對值,單獨處理零輸入,必要時交換兩個輸入。得到絕對值的係數之後,再調整它們的符號與位置,以便用原先的輸入表示最大公因數。兩個輸入均為零時,需要在正輸入定理之外明確給出一個約定。
為甚麼二進制位給出正確的分解
把當前指數寫成商的兩倍加上一個二進制位,便分離出了它的最低位二進制數字。若該位為一,則把當前底數的一個副本移入累積器。剩餘的指數是偶數,所以它的貢獻透過對底數平方並將指數減半來表示。若該位為零,則不移動任何副本,但平方與減半仍然保持總的冪不變。因此每次迭代恰好消耗一個二進制位。
這一推導比死記一連串奇偶判斷與平方更清楚地解釋了該算法。它亦處理了指數為零的情形,而無須事後臨時編造一個數學恆等式:迴圈甚麼也不做,未完成的指數已經是零,累積器為一就是正確的空積。這一計算約定與零次冪的代數定義一致。
在每一階段,累積器與底數都可以約化到標準剩餘範圍。這便把所存數值的大小限制在模數以內,儘管未約化的冪可能極其龐大。指數並不對作為值的模數取模;它是按其二進制表示不斷減半的。這就是該算法對非單位的底數同樣適用的原因,包括與模數有公因數的底數。歐拉(Euler)式的指數約化與二進制冪運算是兩種不同的方法,其假設也各不相同。
概念視角結構
平方求冪需要結合律
冪的不變式在不改變乘法次序的前提下重新組織了重複的乘法。只要在相應的環境中詮釋冪與累積器,同一思想適用於矩陣或任何帶單位元的結合乘法。模運算的版本還在每次乘積之後約化代表元。它不需要任何乘法逆元,因此該方法比關於單位階的定理適用範圍更廣。
運算次數取決於輸入的編碼
一個整數的數值與其編碼的長度是不同的度量。一個只有幾百個二進制位的數,其數值可以極其龐大。因此,一個對不超過該數值的每個整數各執行一次迭代的算法,即使輸入字串很短,也可能不可行。二進制冪運算的迴圈就指數的編碼長度而言是高效的,因為每次迭代去掉一個二進制位。
模數影響每次迭代的成本。位數更多的剩餘需要更多的工作來相乘和約化。算術運算次數把控制結構單獨分離出來,而位元界則把它與某種特定的乘法和約化方法結合起來。更快的整數算術可以降低每次運算的成本,而無須改變迴圈不變式的證明。反過來,使用低效的表示可能令實現的效能變差,卻不會改變數學上的正確性。
對歐幾里得算法的對數次除法,也應以同樣嚴謹的態度來理解。這些除法涉及大小不斷變化的整數,精確的位元分析必須考慮這些大小以及所選用的算術常式。這裏證明的結果保證了除法序列很短,而不是每次除法的成本為常數。當比較輸入為大整數而非小的機器字長數值的算法時,這一區別尤為重要。
計算之後的驗證
模冪的結果,可以在已知某個小循環時與獨立推出的循環核對,也可以與例題中指數的第二種分解核對。然而,一般的正確性證明來自不變式,其適用範圍超出這些方便的例子。同樣,所報告的逆元應當透過將它與原剩餘相乘並對模數約化來檢驗。這最後一步直接驗證了答案的定義性質。
對於所報告的最大公因數證書,應檢查兩個原先輸入的整除性以及精確的線性組合等式。這些檢查對發現符號錯誤與更新次序錯誤特別有效。它們之所以簡短,是因為證明已經說明了它們為何蘊含所要的結論。好的驗證以數學規格為指引,而不是機械地重複實現中的每一行。
常見錯誤
常見錯誤
(在舊值被使用前就覆蓋它)
這些公式中的賦值是同時進行的。在一般程式碼中,應使用暫存變量或謹慎排序的賦值;若在舊值被使用之前便覆蓋了某個係數,就會破壞證書不變式。
常見錯誤
(對指數線性,對其長度卻是指數級)
效率還取決於輸入的表示。指數 約有 個二進制位,因此將 自乘 次,就指數的輸入長度而言,可能需要指數級數量的運算。二進制冪運算就該長度而言使用線性數量的模乘法。若 有 位,則兩個 位剩餘的學校乘法與初等約化需要 次位元運算,因此當 時,這一實現的位元成本為 。這個界限針對的是一種特定的算術方法;它並不表示每個軟件程式庫都使用該方法。
反例模式
指數約化需要底數是單位
聲稱:對所有 與所有 ,都有 。取 、、。則 而 ,於是該說法預言 ;但 。被丟掉的是歐拉定理的假設 ,這裏 。有了這個假設,,把 寫成 便知約化成立。二進制冪運算不需要這個假設:對 ,其狀態 依次為 、、,並正確地返回 。
總結
歐幾里得算法保持因數資訊以及線性組合證書。二進制冪運算保持一個含有未完成指數的乘積。在每種情形下,遞減的整數度量證明終止性,而明確聲明的成本模型使複雜度的陳述有意義。
練習
快速檢查
(利用整數證書,求 模 的逆元。)
必須檢驗最後的同餘式。
解答 · 答案
,,,。回代得 。因此逆元是 ; 驗證了這一點。
快速檢查
(用逐次平方計算 ,並說明為何把指數 對 取模不是一般的規則。)
指數的循環與作為值的模數是不同的對象。
解答 · 答案
模 ,,,。由於 ,所以 。指數約化必須使用諸如 這樣的返回指數,而不是模數 。確實,指數 與 模 同餘,但 而 。
快速檢查
(對 、 執行擴展歐幾里得算法。給出最大公因數與一個證書,並判斷 模 是否可逆。)
同時數一數除法次數;最後一個非零餘數就是答案。
解答 · 答案
,,,,,所以經過五次除法得 。回代得 ;確實 。由於最大公因數是 而不是 , 模 沒有逆元:每個組合 都是偶數,不可能等於 。