Euclid's Algorithm

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 E. (Euclid's Algorithm).

PE1. ECMAScript PE2. ECMAScript PE3. ECMAScript PE4. ECMAScript PE5. ECMAScript

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

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

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

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

function gcd(m, n) {
  assert(isPosInt(m) && isPosInt(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 isPosInt(n) {
  return isInt(n) && n > 0;
}

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

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

function gcd(m, n) {
  assert(isPosInt(m) && isPosInt(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 isPosInt(n) {
  return isInt(n) && n > 0;
}

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

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

function gcd(m, n) {
  assert(isPosInt(m) && isPosInt(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 isPosInt(n) {
  return isInt(n) && n > 0;
}

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

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

function gcd(m, n) {
  assert(isPosInt(m) && isPosInt(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 isPosInt(n) {
  return isInt(n) && n > 0;
}

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

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

ALGORITHM DEK1.1E

from TAOCP, VOL. 1 (1973) by DONALD E. KNUTH