更相減損法
更相減損法，是出自《九章算術》的一種求最大公約數的算法，它原本是為約分而設計的，但它適用於任何需要求最大公約數的場合。又名"更相減損術"，輾轉相減法，等值算法，尼考曼徹斯法。它廣泛應用在數學和計算機上。[1]
| 更相減損法 | |
|---|---|
目錄
概述
古法探源
更相減損法,又稱"等值算法"
"關於約分問題,實質是如何求分子,分母最大公約數的問題.《九章算術》中介紹了這個方法,叫做"更相減損術",即"可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。"
翻譯成現代語言如下:[2]
第一步:任意給定兩個正整數;判斷它們是否都是偶數。若是，則用2約簡;若不是則執行第二步。
第二步:以較大的數減較小的數，接着把所得的差與較小的數比較，並以大數減小數。繼續這個操作，直到所得的減數和差相等為止。
則第一步中約掉的若干個2與第二步中等數的乘積就是所求的最大公約數。
其中所說的"等數"，就是最大公約數。求"等數"的辦法是"更相減損"法。所以更相減損法也叫等值算法。
數學家劉徽對此法進行了明確的註解和說明,是一個實用的數學方法,中學生應該掌握它。
今有九十一分之四十九,問約之得幾何?
我們用(91,49)表示91和49的最大公約數.按劉徽所說,分別列出分子,分母,"以少減多,更相減損,求其等也,以等數約之,等數約之,即除也,其所以相減者皆等數之重疊,故以等數約之."譯文如下:約分的法則是:若分子、分母均為偶數時，可先被2除，否則，將分子與分母之數列在它處，然後以大數減小數，輾轉相減，求它們的最大公約數，用最大公約數去約簡分子與分母。其與古希臘歐幾里德所著的《幾何原本》中卷七第一個命題所論的相同。列式如下:
91≡42(mod49)
49≡7(mod42)
7│42
這裡得到的7就叫做"等數",91和49都是這等數的重疊(即倍數),故7為其公約數.而7和7的最大公約數就是7,(7,7)=7,所以 (91,49)=(42,7)=(7,7)=7
更相減損術在現代仍有理論意義和實用價值.吳文俊教授說:"在我國,求兩數最大公約數即等數,用更相減損之術,將兩數以小減大累減以得之,如求24與15的等數,其逐步減損如下表所示: (24,15)->(9,15)->(9,6)->(3,6)->(3,3)
每次所得兩數與前兩數有相同的等數,兩數之值逐步減少,因而到有限步後必然獲得相同的兩數,也即所求的等數,其理由不證自明.
這個寓理於算不證自明的方法,是完全構造性與機械化的盡可以據此編成程序上機實施".吳先生的話不僅說明了此法的理論價值,而且指明學習和研究的方向.
更相減損法很有研究價值,它奠定了我國漸近分數,不定分析,同餘式論和大衍求一術的理論基礎，望能仔細品味。
比較其他算法
輾轉相除法
(1)兩者都是求最大公因數的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數上輾轉相除法計算次數相對較少，特別當兩個數字大小區別較大時計算次數的區別較明顯。
(2)從結果體現形式來看，輾轉相除法體現結果是以相除餘數為0則得到，而更相減損術則以減數與差相等而得到。
更相損減法在兩數相差較大時，時間複雜度容易退化成O(N)，而輾轉相除法可以穩定在O(logN)。但輾轉相除法需要試商，這就使得在某些情況下，使用更相損減法比使用輾轉相除法更加簡單。而stein算法便由此出現。
Stein算法
(部分內容出自CSDN博主Holmofy) 輾轉相除法是計算兩個數最大公約數的傳統算法，無論從理論還是從實際效率上都是很好的。但是卻有一個致命的缺陷，這個缺陷在素數比較小的時候一般是感覺不到的，只有在大素數時才會顯現出來:一般實際應用中的整數很少會超過64位(當然已經允許128位了)，對於這樣的整數，計算兩個數之間的模是很簡單的。對於字長為32位的平台，計算兩個不超過32位的整數的模，只需要一個指令周期，而計算64位以下的整數模，也不過幾個周期而已。但是對於更大的素數，這樣的計算過程就不得不由用戶來設計，為了計算兩個超過64位的整數的模，用戶也許不得不採用類似於多位數除法手算過程中的試商法，這個過程不但複雜，而且消耗了很多CPU時間。對於現代密碼算法，要求計算128位以上的素數的情況比比皆是，比如說RSA加密算法至少要求500bit密鑰長度，設計這樣的程序迫切希望能夠拋棄除法和取模。
Stein算法很好的解決了輾轉相除法中的這個缺陷，Stein算法只有整數的移位和加減法。下面就來說一下Stein算法的原理:
若a和b都是偶數，則記錄下公約數2，然後都除2(即右移1位); 若其中一個數是偶數，則偶數除2，因為此時2不可能是這兩個數的公約數了 若兩個都是奇數，則a = |a-b|，b = min(a,b)，因為若d是a和b的公約數，那麼d也是|a-b|和min(a,b)的公約數。 Stein算法比輾轉相除法更加快速，簡易。它與每一次進行更相減損法得到的結果似乎存在着微妙的聯繫，通過下面的比較，可以發現兩種算法之間的聯繫。
更相減損法:操作 甲數 乙數 Stein算法:操作 甲數 乙數 98 63 98 63 98-63=35 63 35 98是偶數，除以2 49 63 63-35=28 35 28 都是奇數，63-49=14 49 14 35-28=7 28 7 14是偶數，除以2 49 7 28-7=21 7 21 49-7=42 42 7 21-7=14 7 14 42是偶數，除以2 21 7 14-7=7 7 7 21-7=14 14 7
7-7=0 7 0 14是偶數，除以2 7 7 7-7=0 7 0