經過一些實驗和搜索，我想出了以下定義：
emcd' :: Integer -> Integer -> (Integer,Integer,Integer)
emcd' a 0 = (a, 1, 0)
emcd' a b =
let (g, t, s) = emcd' b r
in (g, s, t - (q * s))
where
(q, r) = divMod a b
- 這個表達背后的含義是
t - (q * s)什么？
我已經嘗試手動評估它；即使我得到了正確的結果(1, -4, 15)，我也不明白為什么該運算式回傳 的值t。
以下是計算一個著名的方法s和t在as bt = gcd(a, b)。在尋找gcd的程序中，我得到了幾個方程。
通過顛倒歐幾里德演算法中的步驟，可以找到這些整數a和b。這些結果方程看起來像運算式t - (q * s)；但是，我無法弄清楚確切的程序。
uj5u.com熱心網友回復：
因為(q, r) = divMod a b，我們有方程
a = qb r
由于遞回呼叫，我們有：
tb sr = g
代a-qb用于r在第二方程中，該裝置
tb s(a-qb) = g
tb sa - qsb = g
sa (t-qs)b = g
這解釋了為什么s并且t - q*s是回傳的好選擇。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/387013.html
下一篇：評估擴展歐幾里得演算法的實作