经过一些实验和搜索,我得出了以下定义:
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
的值。
在as + bt = gcd(a, b)
中有一种著名的计算s
和t
的方法。在寻找gcd的过程中,我得到了几个方程。
通过颠倒欧几里得算法中的步骤,可以找到这些整数a
和b
。这些结果方程看起来像表达式t - (q * s)
;然而,我不知道确切的过程。
由于(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
是返回的好选择。