* Euclid's algorithm (Page 2-9) ** Calculates the greatest common divisor of two numbers. ** Definition *** E0. [Ensure m >= n.] If m < n, exchange m <-> n. *** E1. [Find remainder.] Divide m by n and let r be the remainder. *** E2. [Is it zero?] If r = 0, the algorithm terminates; n is the answer *** E3. [Reduce.] Set m <- n, n <- r, and go back to step E1. ** Use *** Own example: m = 235; n = 95; **** 235 % 95 = 45 **** r = 45 **** m = 95; n = 45; **** 95 % 45 = 5 **** r = 5 **** m = 45; n = 5; **** 45 % 5 = 0 **** r = 0 **** answer = n = 5 *** Knuth example: m = 119; n = 544 **** m = 544; n = 119; **** 544 % 119 = 68 **** r = 68 **** m = 119; n = 68; **** 119 % 68 = 51 **** r = 51 **** m = 68; n = 51; **** 68 % 51 = 17 **** r = 17 **** m = 51; n = 17; **** 51 % 17 = 0 **** r = 0 **** answer = n = 17