概述
古法探源
更相減損法,又稱"等值算法"
“關於約分問題,實質是如何求分子,分母最大公約數的問題.《九章算術》中介紹了這個方法,叫做”更相減損術”,即“可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。”
翻譯成現代語言如下：
第一步：任意給定兩個正整數；判斷它們是否都是偶數。若是，則用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 |
相關程式
Basic程式
C語言程式
已知兩個不大於maxint型正整數a,b,求其最大公約數。（ a,b不一定是偶數）
