On Dienstag, 11. Dezember 2012, 14:53:28, Zbigniew Stanasiuk wrote:
Hallo everyone,
I try to understand how the following recursive function works:
extGCD :: Integer -> Integer -> [Integer] extGCD a 0 = [1, 0, a] extGCD a b = let (q, r) = a `quotRem` b [s, t, g] = extGCD b r in [t, s - q * t, abs g]
Some hints to explain??
It should return a triple rather than a list. That said, the function should have the property extGCD a b = [s, t, g] <=> g = gcd a b and s*a + t*b = g ++++ Now, we prove that property by induction on the absolute value of b. It is easily checked in the case that b = 0. extGCD a 0 = [1, 0, a]; gcd a 0 = a, and 1*a + 0*0 = a Suppose it holds for all (x, y) with |y| < |b|. Then if (q,r) = a `quotRem` b we have |r| < |b|, hence for [s, t, g] = extGCD b r we have 1. g = gcd b r 2. s*b + t*r = g by the induction hypothesis. Now, gcd a b = gcd (q*b + r) b = gcd r b = gcd b r = g and g = s*b + t*r = s*b + t*(a - q*b) = t*a + (s - q*t)* b c.q.f.d.