Algorithm 1.1E

2

BASIC CONCEPTS

ALGORITHMS

1.1

Algorithm E. (Euclid's Algorithm). Given two positive integers m and n, find their greatest common divisor, i.e., the largest positive integer which 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.	[Interchange.] Set m ← n, n ← r, and go back to step E1. ❚

Simulation E. (Euclid's Algorithm).

The GCD of m and n is ...

m
n
r

next slow fast

Count: ?

Program En. (Euclid's Algorithm).

E1. ECMAScript E2. ECMAScript E3. ECMAScript E4. ECMAScript E5. ECMAScript

function gcd(m, n) {
  assertTrue(isPositiveInt(m) && isPositiveInt(n));
  let r = undefined;
  while (true) {
    r = m % n;
    if (r === 0) {
      return n;
    }
    m = n;
    n = r;
  }
}

function isPositiveInt(n) {
  return isInt(n) && n > 0;
}

function isInt(n) {
  return n === parseInt(n);
}

function assertTrue(condition) {
  if (!condition) {
    throw Error('assertion failed');
  }
}

function gcd(m, n) {
  assertTrue(isPositiveInt(m) && isPositiveInt(n));
  let r = mod(m, n);
  if (r === 0) {
    return n;
  }
  else {
    return gcd(n, r);
  }
}

function mod(m, n) {
  let r = m;
  while (r >= n) {
    r = r - n;
  }
  return r;
}

function isPositiveInt(n) {
  return isInt(n) && n > 0;
}

function isInt(n) {
  return n === parseInt(n);
}

function assertTrue(condition) {
  if (!condition) {
    throw Error('assertion failed');
  }
}

function gcd(m, n) {
  assertTrue(isPositiveInt(m) && isPositiveInt(n));
  let r = mod(m, n);
  if (r === 0)
    return n;
  return gcd(n, r);
}

function mod(m, n) {
  let r = m;
  while (r >= n)
    r = r - n;
  return r;
}

function isPositiveInt(n) {
  return isInt(n) && n > 0;
}

function isInt(n) {
  return n === parseInt(n);
}

function assertTrue(condition) {
  if (!condition) {
    throw Error('assertion failed');
  }
}

function gcd(m, n) {
  assertTrue(isPositiveInt(m) && isPositiveInt(n));
  let r = mod(m, n);
  return (r === 0) ? n : gcd(n, r);
}

function mod(m, n) {
  let r;
  for (r = m; r >= n; r = r - n) {
  }
  return r;
}

function isPositiveInt(n) {
  return isInt(n) && n > 0;
}

function isInt(n) {
  return n === parseInt(n);
}

function assertTrue(condition) {
  if (!condition) {
    throw Error('assertion failed');
  }
}

function gcd(m, n) {
  assertTrue(isPositiveInt(m) && isPositiveInt(n));
  let r = mod(m, n);
  return (r === 0) ? n : gcd(n, r);
}

function mod(m, n) {
  for (var r = m; r >= n; r -= n);
  return r;
}

function isPositiveInt(n) {
  return isInt(n) && n > 0;
}

function isInt(n) {
  return n === parseInt(n);
}

function assertTrue(condition) {
  if (!condition) {
    throw Error('assertion failed');
  }
}

EXERCISES

1. When translating the ECMAScript programs above into the Java programming language, why is it not necessary to include a translation of the function isInt?
2. Create a Java class called Util with methods mod, isPositiveInt, and assertTrue. For each method, provide a Java implementation that is analogous to the corresponding ECMAScript function. What factors did you consider when deciding whether to make the methods static?
3. Translate the ECMAScript programs E1-4 above into the Java programming language by creating a class called OkayMath that has methods gcd1, ..., gcd4 and uses the Util class you created in the previous exercise.
4. Create an ECMAScript variation of program E1 called gcd1DoWhile that uses a “do-while” loop instead of a while loop. Translate the ECMAScript program into Java.
5. Create a more efficient ECMAScript variation of program E1 called gcd1FasterWhile that also uses a while loop but evaluates another expression instead of true. How is your program more efficient than program E1?
6. Using a for loop instead of a while loop, create an ECMAScript program called gcd1FasterFor that is otherwise identical to the one you created in the previous exercise.
7. Create a Java class called FasterMath that extends OkayMath (created in a previous exercise) and has a method that overrides OkayMath.gcd1 with a Java translation of one of the two ECMAScript functions you created in the previous two exercises.

ALGORITHM E

from TAOCP Vol. 1 (1973) by Donald Ervin Knuth