Taking conjuncts as invariant 0

Our derivation of Euclid's algorithm was pretty involved. Let's spend some time practicing some simpler derivations.

Continued

Euclid, via Knuth

The very first algorithm we encounter in The Art of Computer Programming is Euclid's formula for the greatest common divisor. Euclid's algorithm is actually a family of algorithms, one of which Knuth describes below.

Algorithm E ( Euclid's algorithm). Given two positive integers m and n,
find their greatest common divisor, that is, the largest positive integer that
evenly divides both m and n.

E1 [Find remainder.] Divide m by n and let r be the remainder.
(We will have 0 ≤ r < n)
E2 [Is it zero?] If r=0, the algorithm terminates: n is the answer.
E3 [Reduce.] Set m← n, n&larr r, and go back to step E1.


Knuth's presentation is somewhat unfortunate, as it begs the question - where did it come from? In his preface to volume one Knuth writes `... I am not trying to teach the reader how to use somebody else's software. I am concerned rather with teaching people how to write better software themselves.'
In that spirit, let us see how we might produce this algorithm ourselves.

Continued