art-of-computer-programming/chapter-1/notes.org

* 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