輾轉相除法

<a href="http://zh.wikipedia.org/wiki/File:Euklid.jpg" target="_blank"></a>

算法描述

　　兩個數a，b的最大公約數記為GCD(a,b)。a，b的最大公約數是兩個數的公共素因子的乘積。如462可以分解成2 × 3 × 7 × 11；1071可以分解成3 × 3 × 7 × 17。462和1071的最大公約數等于它們共有的素因數的乘積3 × 7 = 21。如果兩數沒有公共的素因數，那麼它們的最大公約數是1，也即這兩個數互素，即GCD(a,b)=1。另g=GCD(a,b)，則a=mg, b=ng，其中m，n均為正整數。由上述分析可知，m，n互素。因為m，n沒有公共素因子，GCD(m,n)=1。

　　輾轉相除法是一種遞歸算法。設k表示步驟數（從0開始計數），算法的計算過程如下。每一步的輸入是都是前兩次計算的餘數rk−1和rk−2。因為每一步計算出的餘數都在不斷減小，是以，rk−1小于rk−2。在第k步中，算法計算出滿足以下等式的商qk和餘數 rk：

<dl><dd>rk−2 = qk rk−1 + rk</dd></dl>

其中rk &lt; rk−1。也就是rk−2要不斷減去rk−1直到比rk−1小。

　　在第一步計算時（k = 0），設r−2和r−1分别等于a和b，第2步（此時k = 1）時計算r−1（即b）和r0（第一步計算産生的餘數）相除産生的商和餘數，以此類推。整個算法可以用如下等式表示：

<dl></dl>

<dd>a = q0 b + r0</dd>

<dd>b = q1 r0 + r1</dd>

<dd>r0 = q2 r1 + r2</dd>

<dd>r1 = q3 r2 + r3</dd>

<dd>…</dd>

　　如果輸入參數a小于b，則第一步計算的結果是交換兩個變量的值：因為a &lt; b，是以a和b相除得到的商q0等于0，餘數r0等于a。是以在運算的每一步中得出的餘數一定小于上一步計算的餘數（rk一定小于rk−1）。由于每一步的餘數都在減小并且不為負數，必然存在第N步時rN等于0，使算法終止，rN−1 就是a和b的最大公約數。其中N不可能無窮大，因為在r0和0之間隻有有限個自然數。

　　輾轉相除法的正确性可以用兩步來證明。首先，算法的最終結果rN−1同時整除a和b。因為它是一個公約數，是以必然小于或者等于最大公約數g。然後，任何a和b的公約數都能整除rN−1。是以g一定小于或等于rN−1。兩個不等式隻在rN−1 = g是同時成立。

算法實作

　　遞歸版本

<a></a>

1 function　gcd(a, b)

2 　　if a&lt;b

3 　　　　swap(a,b);　　

4 　　if b==0

5 　　　　then return a;

6 　　else

7 　　　　return gcd(b, a mod b);

8 end

　　循環版本

1 function gcd(a,b)

3 　　　　then swap(a,b);

4 　　while(b!=0)

5 　　{

6 　　　　c = a mod b;

7 　　　　a = b;

8 　　　　b = c;

9 　　}

10 　　return a;

11 end

擴充歐幾裡德算法

<dd>sk = sk−2 − qk−1sk−1</dd>

<dd>tk = tk−2 − qk−1tk−1</dd>

算法開始時：

<dd>s−2 = 1, t−2 = 0</dd>

<dd>s−1 = 0, t−1 = 1</dd>

加上這個遞歸式後，當算法終止于rN = 0，貝祖等式的整數s和t分别由sN和tN給出。

這個算法的正确性可以用數學歸納法來證明。假設遞歸至第k−1步是正确的，也就是假設：

<dl><dd>rj = sj a + tj b</dd></dl>

對所有j小于k成立。則第k步運算得出以下等式：

<dl><dd>rk = rk−2 − qk−1rk−1</dd></dl>

因為rk−2和rk−1被假定是正确的，是以可以用s和t表示：

<dl><dd>rk = (sk−2 a + tk−2 b) − qk−1(sk−1 a + tk−1 b)</dd></dl>

整理後得到第k步的結果，和我們期望得到的結果一緻：

<dl><dd>rk = sk a + tk b = (sk−2 − qk−1sk−1) a + (tk−2 − qk−1tk−1) b</dd></dl>

算法分析

　　加百利·拉梅于1884年指出，一個算法的效率可以用計算所需步數乘以每步計算的開銷表示。用輾轉相除法計算兩個數的最大公約數所需的步數不會超過其中較小數的位數h的5倍。因為每一步的計算開銷通常也是h數量級的，是以輾轉相除法的複雜度是h2。

計算兩個自然數a和b的最大公約數所需的步數可以表示為T(a, b)。如果a和b的最大公約數是g，m和n是兩個互素整數，使a = mg，b = ng，那麼：

<dl><dd>T(a, b) = T(m, n)</dd></dl>

這可以通過在輾轉相除法的計算過程中的每一步都除以g來證明。同樣，當a和b同時乘以w時，計算步數不變：T(a, b) = T(wa, wb)。是以，對于數值上相近的數，如T(a, b)和T(a, b + 1)，計算步數可能相差很大。

根據輾轉相除法的遞歸性質可以得出另一個公式：

<dl><dd>T(a, b) = 1 + T(b, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1</dd></dl>

并且定義T(x, 0) = 0。

輾轉相除法的平均步驟數有三種不同的定義。第一種定義是計算已知自然數a和從0到a − 1範圍内随機選取的自然數b的最大公約數所需的時間T(a)：

<dl><dd></dd></dl>

但是因為T(a, b)在連續整數間變化非常劇烈，是以T(a)的平均值也會顯得很雜亂。

為了解決這個問題，第二種定義規定τ(a)隻要取遍其中所有和a互素的數即可:

因為第一種定義可以通過用第二種定義的求和來完成：

是以也可以由以下公式近似：

第三種定義Y(n)定義為從1到n間随機選取a和b時計算他們的最大公約數所需的平均步驟數：

将T(a)的近似公式代入，得到Y(n)的近似值：

在輾轉相除法的每一步中，商qk和餘數rk都通過rk−2和rk−1求出：

<dl><dd>rk−2 = qk rk−1 + rk.</dd></dl>

是以每一步的計算開銷主要與計算商qk的算法有關，因為餘數rk可以很迅速地從rk−2、rk−1和qk計算出來：

<dl><dd>rk = rk−2 − qk rk−1.</dd></dl>

綜合考慮算法需要的步數和每一步的計算開銷，輾轉相除法的随兩個數字a和b的平均位數成平方級的速度增長(h2)。設h0、h1、…、hN−1表示計算過程中的餘數r0、r1、…、rN−1的位數，因為算法的步數N随h線性增長，是以算法的運算時間為：

本文轉自NewPanderKing51CTO部落格，原文連結： http://www.cnblogs.com/newpanderking/archive/2011/07/25/2116323.html，如需轉載請自行聯系原作者