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?

Eade

There are a bunch of fun ones here: codegolf.stackexchange.com/questions/35587 – Powerless

Answer 1

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).

Barrick

Thanks. And I googled for a good 20 minute and didn't yield any clear results. – Eade

@JerryCoffin: Why not just template this? – Tailpiece

Answer 2

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.

Telephonist

You shouldn't rely on undocumented features like that as they can change between library releases. – Danczyk

Is it available for MSVC? – Unnatural

@vmrob: Agreed. You can always copy implementation from STL. Mbt925: Done. – Telephonist

that smells like cheating ;) – Danelledanete

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.

Bellboy

+1 You can even add template<class Integral> to replace the int, add a constexpr keyword before the function and you have a nice compile-time/runtime generic function. – Gwendolyngweneth

Possible typo in your second method. Should it return n1? n2 will by definition always be zero at that point. – Romanov

Good catch, @Jim, fixed that up. – Bellboy

Answer 4

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

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

Stanza

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;
}

Anatolian