GCD function in c++ sans cmath library

Question

I'm writing a mixed numeral class and need a quick and easy 'greatest common divisor' function. Can anyone give me the code or a link to the code?

Answer 1

The libstdc++ algorithm library has a hidden gcd function (I'm using g++ 4.6.3).

#include <iostream>
#include <algorithm>

int main()
{
  std::cout << std::__gcd(100,24); // print 4
  return 0;
}

You are welcome :)

UPDATE: As @chema989 noted it, in C++17 there is std::gcd() function available with <numeric> header.

Answer 2

I'm tempted to vote to close -- it seems difficult to believe that an implementation would be hard to find, but who knows for sure.

template <typename Number>
Number GCD(Number u, Number v) {
    while (v != 0) {
        Number r = u % v;
        u = v;
        v = r;
    }
    return u;
}

In C++ 17 or newer, you can just #include <numeric>, and use std::gcd (and if you care about the gcd, chances are pretty fair that you'll be interested in the std::lcm that was added as well).

Answer 3

A quick recursive version:

unsigned int gcd (unsigned int n1, unsigned int n2) {
    return (n2 == 0) ? n1 : gcd (n2, n1 % n2);
}

or the equivalent iterative version if you're violently opposed to recursion ^(a):

unsigned int gcd (unsigned int n1, unsigned int n2) {
    unsigned int tmp;
    while (n2 != 0) {
        tmp = n1;
        n1 = n2;
        n2 = tmp % n2;
    }
    return n1;
}

Just substitute in your own data type, zero comparison, assignment and modulus method (if you're using some non-basic type like a bignum class, for example).

This function actually came from an earlier answer of mine for working out integral aspect ratios for screen sizes but the original source was the Euclidean algorithm I learnt a long time ago, detailed here on Wikipedia if you want to know the math behind it.

---

^(a) The problem with some recursive solutions is that they approach the answer so slowly you tend to run out of stack space before you get there, such as with the very badly thought out (pseudo-code):

def sum (a:unsigned, b:unsigned):
    if b == 0: return a
    return sum (a + 1, b - 1)

You'll find that very expensive on something like sum (1, 1000000000) as you (try to) use up a billion or so stack frames. The ideal use case for recursion is something like a binary search where you reduce the solution space by half for each iteration. The greatest common divisor is also one where the solution space reduces rapidly so fears about massive stack use are unfounded there.

Answer 4

For C++17 you can use std::gcd defined in header <numeric>:

auto res = std::gcd(10, 20);

Answer 5

The Euclidean algorithm is quite easy to write in C.

int gcd(int a, int b) {
  while (b != 0)  {
    int t = b;
    b = a % b;
    a = t;
  }
  return a;
}