Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. extended gcd (Zbigniew Stanasiuk)
2. Re: extended gcd (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Tue, 11 Dec 2012 14:53:28 +0100
From: Zbigniew Stanasiuk <[email protected]>
Subject: [Haskell-beginners] extended gcd
To: [email protected]
Message-ID:
<capowojdeorrz9np6vldlwqtxncjdrag5g3dbx6qfktbkaoy...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
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??
Regards,
Z.Stanasiuk
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121211/95985509/attachment-0001.htm>
------------------------------
Message: 2
Date: Tue, 11 Dec 2012 15:16:18 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] extended gcd
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
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.
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 54, Issue 17
*****************************************
