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
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
posted by Eric at 1:05 PM
0 Comments:
Post a Comment
<< Home