#include <cstdio>
#include <cstdlib>
#include <string>

/*
 * Euclid's algorithm.
 */
unsigned long euclide(unsigned long m, unsigned long n) {

  while (n != 0) {
    unsigned long t = n;
    n = m % n;
    m = t;
  }
  return m;
}

/*
 * Stein's binary algorithm.
 */
unsigned long binary(unsigned long m, unsigned long n) {
  unsigned long twos = 0;

  if (m == 0) return n;
  if (n == 0) return m;

  // Find common multiplicity of two.
  while (((m | n) & 1) == 0) {
    m >>= 1;
    n >>= 1;
    twos++;
  }

  // Make m odd.
  while ((n & 1) == 0) n >>= 1;

  while (m != 0) {
    while ((m & 1) == 0) m >>= 1;

    if (m < n) {
      std::swap(m, n);
    }

    m -= n;
    m >>= 1;
  }

  return n << twos;
}

int main(void) {

  // Some sanity tests.
  for (int i = 0; i < 1000000; i++) {
    int m = rand();
    int n = rand();

    if (binary(m, n) != euclide(m, n)) {
      printf("euclide(%lu, %lu) = %lu\n", m, n, euclide(m, n));
      printf("binary(%lu, %lu) = %lu\n", m, n, binary(m, n));
    }
  }
}