Greatest Common Divisor

Greatest Common Divisor

最大公因數。多個數字共同都有的正因數當中最大的一個。

Least Common Multiple

最小公倍數。多個數字共同都有的正倍數當中最小的一個。

Greatest Common Divisor: Euclid's Algorithm

Euclid's Algorithm(Euclidean Algorithm)

幾何學之父歐幾里德所發明的「輾轉相除法」,用來求兩個數的最大公因數。幾何學之父原來跟數論也扯得上關係。

由於兩個數必定是由最大公因數的整數倍所組合而成,故其差值也必定由最大公因數的整數倍所組合而成,不管兩數如何輾轉相減、輾轉求餘數,其得到的值都會是最大公因數的倍數。把最大公因數想成是萬丈高樓平地起的磚塊們就簡單多了。

求出了差值後,原問題便縮小成了跟原問題類似的問題。也就是說,輾轉相除法採取了Divide and Conquer的策略。

時間複雜度

時間複雜度是O(logB),其中B是兩數中較小的那個數。時間複雜度可用Fibonacci Sequence算得,詳情可參考離散數學的書籍。

程式碼

迴圈版本。

另一種奇怪的迴圈版本。僅供參考。

遞迴版本。

寫的很簡略。自己實做時,敬請注意參數的數值範圍。

UVa 10193 10407

Greatest Common Divisor: Extended Euclid's Algorithm

Extended Euclid's Algorithm(Extended Euclidean Algorithm)

畫蛇添足的輾轉相除法,中文翻譯成「擴充歐幾里德演算法」。它除了可以找出兩數的最大公因數,還可以順便找出此兩數各乘上多少倍率後相加可得到最大公因數(倍率可以是負數或零),並且讓兩個倍率的絕對值相加後最小。

以數學符號來表示的話,這個演算法可找出a b兩數的最大公因數d,以及順便找出滿足a*i + b*j = d的兩個倍率i j,且讓|i|+|j|會最小。

想像一下萬丈高樓平地起的模型。由於a b兩數都是最大公因數的倍數,所以a的倍數a*i、b的倍數b*j兩數也會是最大公因數的倍數囉。然後,同之前文章所述,a*i、b*j兩數不管如何輾轉相減,都會是最大公因數的倍數。所以要找到符合條件的i j,讓a*i、b*j兩數的和(差)剛好是最大公因數的一倍,應該是滿有可能的事情。

以下整理出兩種解決方式。

Iterative

首先分別複製a b到c d上面,以c d兩數來輾轉相除。然後設計另外兩個倍率i' j',並令每次輾轉相除時都保持a*i' + b*j' = c且a*i + b*j = d。

由於a*i' + b*j' = c且a*i + b*j = d,及每次做除法的式子r = c - q*d,可推得 r = c - q*d = (a*i' + b*j') - q * (a*i + b*j) = a * (i'-q*i) + b * (j'-q*j)。如此一來,在輾轉相除時,就知道i j兩數如何隨著r做變動了。

至於為什麼|i|+|j|會最小呢?我也不知道。

Recursive(Divide and Conquer)

要計算i j,可利用Divide and Conquer的Merge階段來做:當問題分割至最小的時候,可以很明確的、輕鬆的算出i j的值;每次將小問題合併時,便重新調整i j的值,並保持|i|+|j|最小;當合併至原來的問題時,得到的i j即是所求。

Modular Inverse

Extended Euclid's Algorithm也可以用來計算:當a m已知時,令a*i ≡ 1 (mod m)的i。方法是將原式改寫成a*i + m*j = 1即可。

來一點題目。

UVa 10090 10104

Greatest Common Divisor: Binary GCD Algorithm

Binary GCD Algorithm

二進位數字的最大公因數計算方法。

如果 a b 有一個是零     -> gcd(a, b) = a 和 b 當中不是零的那ㄧ個數
如果 a b 都是偶數       -> gcd(a, b) = gcd(a/2, b/2) * 2;
如果 a 是偶數  b 是奇數 -> gcd(a, b) = gcd(a/2, b)
如果 a 是奇數  b 是偶數 -> gcd(a, b) = gcd(a, b/2)
如果 a b 都是奇數       -> gcd(a, b) = gcd(a 和 b 比較小那個, a 和 b 的差);

電腦裡的數字都是用二進位儲存的──要乘以二,就把數字的每個bit都左移一個bit;要除以二,就把數字的每個bit都右移一個bit(別忘記補零)。位移運算比除法運算、模數運算還要快,於是便開發了以提取因數二來計算最大公因數的方法。

歸納要點:一、不斷提取共同的因數,都只提取二;二、二與奇數互質,不會影響最大公因數,故可除去二;三、若無因數二則相減,相減後仍是最大公因數的倍數。

時間複雜度是O((logAB)^2),AB為a b兩數的乘積。【待補證明】【待補速度討論】

程式碼

這裡提供幾支程式碼供大家參考。首先是迴圈版本。

遞迴版本。

按照TAOCP的建議,然後我自己實作的版本。

維基百科:http://en.wikipedia.org/wiki/Binary_GCD_algorithm#Implementation_in_C上面也有一版。如果各位有更快更好的實作方法,歡迎提供。謝謝大家收看。