理解扩展欧几里得算法的实现



经过一些实验和搜索,我得出了以下定义:

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)中有一种著名的计算st的方法。在寻找gcd的过程中,我得到了几个方程。

通过颠倒欧几里得算法中的步骤,可以找到这些整数ab。这些结果方程看起来像表达式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

这就解释了为什么st - q*s是返回的好选择。

最新更新