用Python 3實現歐幾里德算法

上回提要：喺Python 3裡面用蒙地卡羅方法估算圓周率

http://hkgalden.com/view/298369/highlight/6875

閱讀本文前請先喺Tampermonkey/Greasemonkey安裝MathJax for HKGalden 以達致最好嘅閱讀體驗
https://openuserjs.org/install/Karho/MathJax_for_HKGalden.user.js

大家好，今次要同大家講下點用Python 3寫出唔同形式嘅 歐幾里德算法（Euclidean algorithm，簡稱EA）
所謂EA，其實就係利用基本算法搵出兩個數字嘅 最大公因數（Highest Common Factor/ Greatest Common Divisor）
喺內文主要會同大家探討兩種類形嘅歐幾里德算法，一種係牽涉兩個數字嘅EA，同埋牽涉三個數字嘅EA

不過，三個數字嘅EA只不過係本人自己估出來，未經過嚴謹嘅數學驗證

喺正式討論EA之前，先同大家重溫下乜野係餘數（remainder）

所有整數`p`都可以寫成以下呢個形式
`p=q cdot s+r`
例如`24`可以寫成`24=5 cdot 4 + 4`又或者`24=7 cdot 3 + 3`，如此類推

如果將`24`除以`5`或者`4`，我哋會得出餘數`4`，而如果將`24`除以`7`或者`3`，我哋會得出餘數`3`

喺編程語言嘅世界裡面有個專計餘數嘅函式（function）或者 運算子（operator），分別係"mod"函式同 "%"運算子

例如，24 mod 5 或者 24 % 5 會等於4，24 mod 3 或者 24 % 3會等於3
如果用數學算式表示p mod q 或者 p % q 就即係
`p - floor{p/q} cdot q`
（`floor{cdot}`即係取嗰個數字最近而且大過嘅一個整數）

講返正題，歐幾里德算法（EA）被認為係算法嘅始祖，全因歐幾里德呢條友喺大概公元前三百年已經喺佢本《幾何原本》記載過呢個算法
我哋一齊來睇睇喺Python 3裡面點用EA


def euclid(x, y):
    while y != 0:
        t = y
        y = x % y
        x = t
    return x

euclid(16, 28)


呢個版本係無 遞迴（recursion）喺入面嘅，我哋輸入16同28呢兩個數字入去"euclid"函式，就會得到"4"呢個結果 


def euclid(x, y):
    while y != 0:
        t = y
        y = x % y
        x = t
    return x

我哋喺度定義"euclid"為一個要求兩個整數參數嘅函式，只要y唔係等於0，就會不停執行迴圈裡面嘅算法，最後會回傳x畀呼叫呢個函式嘅敘述 
我哋可以跟蹤下呢個程式係點運作 

euclid(16, 28) -> x = 16, y = 28
----------------------------
y = 28 -> y != 0
t = 28
y = 16 % 28 = 16
x = 28 -> x = 28, y = 16（調咗位 ）
----------------------------
y = 16 -> y != 0
t = 16
y = 28 % 16 = 12
x = 16 -> x = 16, y = 12
----------------------------
y = 12 -> y != 0
t = 12
y = 16 % 12 = 4
x = 12 -> x = 12, y = 4
----------------------------
y = 4 -> y != 0
t = 4
y = 12 % 4 = 0
x = 4 -> x = 4, y = 0
----------------------------
y = 0 -> y == 0
return x -> return 4
euclid(16, 28) = 4

使用以上嘅算法就可以搵到16同28嘅最大公因數啦 

跟住落來會同大家講下點樣用遞迴版嘅EA啦，望下最簡單嘅版本先 

def euclid(x, y):
    if x > y:
        return euclid(x - y, y)
    elif x < y:
        return euclid(x, y - x)
    else:
        return x


我哋一齊跟蹤下呢個程式點運作 

euclid(10, 4) -> x = 10, y = 4
x > y -> return euclid(x - y, y)
    -> return euclid(6, 4) --&gt; x = 6, y = 4
    --&gt; x > y --&gt; return euclid(x - y, y)
    --&gt; return euclid(2, 4) ---&gt; x = 2, y = 4
    ---&gt; x < y ---&gt; return euclid(x, y - x)
    ---&gt; return euclid(2, 2) ----&gt; x = 2, y = 2
    ----&gt; x == y ----&gt; euclid(2, 2) = 2 ---&gt; euclid(2, 4) = 2 --&gt; euclid(6, 4) = 2 -> euclid(10, 4) = 2

我諗你喺睇完呢段程式碼，就會知遞迴嘅意思其實就係一層一層咁搵落去搵到停為止 

以下係遞迴同Python內置函式嘅結合版本 

def euclid(x, y):
    if x != y:
        return euclid(abs(x-y), min([x, y]))
    return y


但係好可惜，如果x同y差距太多就會有以下呢個情況，例如x係2嘅50次方，而y係2，Python 除錯器（Debugger）就會出現以下錯誤
RecursionError: maximum recursion depth exceeded in comparison
錯誤話你知你遞迴嘅次數係有限，所以電腦只能夠幫你遞迴到某個位就停 
即係而家電腦計計下就停咗落來，咁你咪計唔到最後答案囉  
[好似係]
至於點解會有最高遞迴次數，其實就係因為Python編繹器幫程式佔有嘅記憶體數量係有限嘅
如果遞迴次數太高，就會佔用愈多記憶體，甚至可能超過預先Python留畀你嘅限額  
所以Python設有最高遞迴次數，保障你無咁易因為超過記憶體限額而導致有 緩衝溢出（Buffer overflow），令到你部電腦嘅安全受威脅   
[/好似係]

就咁睇，齋用減法同遞迴係唔夠有效，所以都係用返%運算子係最好，但係點解用%運算子，會好過剩係用減號呢
畀個減法嘅例子你望望 

18, 4
14, 4
10, 4
6, 4
2, 4
2, 2
H.C.F. = 2


畀個用%運算子嘅例子你望望

18, 4
2, 4 (where 18%4 = 2)
Since 4 % 2 == 0, H.C.F. = min(2, 4) = 2

用%運算子畀起用減法會快好多因為%運算子其實就幫你做多幾次減法  

[#ff0011]以下係用遞迴同%運算子嘅算法[/#ff0011]

def optimized_euclid(x, y):
    if x % y != 0:
        return optimized_euclid(y, x % y)
    else:
        return y

print(optimized_euclid(2**50, 104**5)) ## result = 32768


講完只係牽涉兩個數字嘅EA，就來睇下牽涉三個數字嘅EA啦，一齊睇下我嘅程式碼（待證） 

def euclid3(x, y, z):
    lst = [x, y, z]
    lst.sort()
    mmax = lst[2]
    mmin = lst[0]
    if lst.count(mmax) == 3:
        mmid = mmax
    else:
        mmid = lst[1]
    print("max =", mmax, ";min =", mmin, "; mid =", mmid)
    if lst.count(mmax) == 2:
        if mmax % mmin == 0:
            return mmin
        else:
            buff = mmax % mmin
            return euclid3(buff, buff, mmin)
    elif lst.count(mmin) == 2:
        if mmax % mmin == 0:
            return mmin
        else:
            buff = mmax % mmin
            return euclid3(buff, mmin, mmin)
    elif x == y and x == z and y == z:
        return mmin
    else:
        return euclid3(mmax % mmid, mmid, mmin)


延伸思考：
1. 究竟我嘅euclid3有冇問題？ 
2. 假設你要寫個牽涉4個數字嘅EA，你會點寫？ 
3. 假設你要寫個牽涉n個數字嘅EA，你會點寫？ 
4. 當n愈來愈大，用質因分解（Prime factorization）幫手搵最大公因數，定用euclidn幫手搵最大公因數會比較有效？

40

2015/10/09, 7:40:50 晚上

本貼文共有 0 個回覆

此貼文已鎖，將不接受回覆

發表文章

發起投票