3
\$\begingroup\$

I wrote a function template to compute the GCD of two integers. This function checks that its arguments are an integral type. I also wrote a function template which accepts a pair of iterators in order to compute the GCD of two or more integers. It calls the first function to compute the GCD of pairs of integers.

Here is the code for the GCD functions, as well as some code in main() to demonstrate and test the use of the functions:

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <list>
#include <iterator>
#include <stdexcept>

/** \brief Computes the greatest common divisor of its arguments.
\tparam integer a type for which
[std::is_integral](http://en.cppreference.com/w/cpp/types/is_integral)
returns `true`
*/
template <typename integer,
    typename = std::enable_if_t<std::is_integral<integer>::value> >
integer gcd(integer a, integer b) {
    // Make sure arguments are positive since gcd is always positive
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    if (a == 0) return b; // gcd(0, b) = |b|

    // Euclid's algorithm
    while (b != 0) {
        if (a > b) a -= b;
        else b -= a;
    }
    return a;
}

/** \brief Computes the greatest common divisor of the integers in the range
[first, last).
\tparam Iter must meet the requirements of
[InputIterator](http://en.cppreference.com/w/cpp/concept/InputIterator)
\tparam integer a type for which
[std::is_integral](http://en.cppreference.com/w/cpp/types/is_integral)
returns `true`
\param[in] first the iterator pointing to the first element
\param[in] last the iterator pointing to one past the last element
\return the greatest common divisor of the integers in the range [first, last)
*/
template <typename Iter, typename integer = typename Iter::value_type>
integer gcd(Iter first, Iter last) {
    auto n = std::distance(first, last);

    if (n < 2) throw std::invalid_argument("must have at least two values");

    // Compute the gcd of the first two integers
    auto d = gcd(*first, *std::next(first));

    // Iterate through remaining integers using the fact that gcd(a, b, c) = gcd(gcd(a, b), c)
    auto iter = std::next(first, 2); // iterator to the third integer

    while (iter != last) {
        d = gcd(d, *iter);
        ++iter;
    }

    return d;
}

int main() {
  std::cout << "Testing the basic gcd():\n";
  std::cout << gcd(4, 8) << "\n";
  std::cout << gcd(54, 24) << "\n";
  std::cout << gcd(-42, 56) << "\n";
  std::cout << gcd(18, -84) << "\n";
  std::cout << gcd(4, 0) << "\n";
  std::cout << gcd(0, 8) << "\n";
  std::cout << gcd(0, 0) << "\n";

  // would correctly result in compile error
  //std::cout << gcd(4.9, 8) << "\n";

  std::cout << "\nTesting the range-based gcd():\n";

  std::vector<int> v;
  std::set<int> s;
  std::list<int> li;

  // Test gcd() with the vector

  try {
      std::cout << gcd(v.begin(), v.end()) << "\n";
  } catch (const std::invalid_argument& e) {
      std::cout << "Correctly caught exception (empty vector): " << e.what() << "\n";
  }

  // Add one element to v
  v.push_back(4);

  try {
      std::cout << gcd(v.begin(), v.end()) << "\n";
  } catch (const std::invalid_argument& e) {
      std::cout << "Correctly caught exception (only one element in vector): " << e.what() << "\n";
  }

  // Add second element to v
  v.push_back(8);
  std::cout << gcd(v.begin(), v.end()) << "\n";

  // Add third element to v
  v.push_back(8);
  std::cout << gcd(v.begin(), v.end()) << "\n";

  // Add fourth element to v
  v.push_back(14);
  std::cout << gcd(v.begin(), v.end()) << "\n";

  try {
      std::cout << gcd(v.begin(), v.begin()) << "\n";
  } catch (const std::invalid_argument& e) {
      std::cout << "Correctly caught exception (v.begin() used for both arguments): " << e.what() << "\n";
  }

  // Test gcd() with the set

  s.insert(8);
  s.insert(4);
  s.insert(14);
  s.insert(-8);
  std::cout << "Using std::set: " << gcd(s.begin(), s.end()) << "\n";

  // Test gcd() with the list

  li.push_back(8);
  li.push_back(4);
  li.push_back(14);
  li.push_back(-8);
  std::cout << "Using std::list: " << gcd(li.begin(), li.end()) << "\n";
}

I'm looking for suggestions to improve any aspect of the code. Some specific questions:

  1. Should the iterator-based gcd() have a different name like multigcd() or is it clear enough to use gcd() for both? Is it confusing that gcd() takes two arguments regardless of how many integers are actually part of the calculation? Any other naming advice?
  2. Are the comments sufficient?
  3. Is std::invalid_argument the correct exception to throw? Is the explanatory string for it sufficiently descriptive?
\$\endgroup\$
1
  • \$\begingroup\$ Are there any other appropriate tags to add? I can't tell if generics or template is the appropriate one, for example. \$\endgroup\$
    – Null
    Feb 18, 2016 at 19:03

2 Answers 2

1
\$\begingroup\$

I think Martin R's suggestion is a good one, but I won't repeat it.

I'll start by considering your questions directly:

  1. As far as the iterator-based gcd goes, my immediate reaction is to wonder whether it should exist at all. It's basically equivalent to using std::accumulate to apply a two-integers GCD function across the collection (with a starting value of 0). The only obvious difference is that std::accumulate doesn't try to check the arguments much. Instead, it'll return 0 for an empty collection, and the one input number if given a collection containing only one number.

  2. The comments worry me a little. In most cases, I find comments to be most useful when they explain things that can't reasonably be expressed directly in the code, such as why I did something, rather than simply what something is doing. Just for example, for the comments in main that delineate what's being tested in each section of the code, I'd rather see each of those broken out into a function with a suitable name, so main would look more like:

    test_scalar_gcd();
    test_reject_float();
    test_range_gcd(v);
    test_range_gcd(s);
    test_range_gcd(l);
    

    Though, of course, if you take the preceding advice and just use the scalar gcd with std::accumulate, most of this probably becomes unnecessary.

    I've never been very excited about Doxygen-style comments, and these strike me as prime examples of why. The fact that integer represents some type for which is_integer returns true seems like the sort of thing that could be buried in a footnote to a point that's raised in an appendix (or something on that order). For the most part, it's an elaborate statement of the obvious. Bottom line, I'm somewhat doubtful about whether these comments really add much (if anything) that's really useful.

  3. I think the exception (and wording you've used) is adequate, but (going back to 1. above), I think it's questionable whether that code is necessary at all. If you do need it, I'd still write it as a wrapper that used std::accumulate internally.

There are a few other things I'd consider. First of all, you've defined one of the template parameters as:

typename integer = typename Iter::value_type

Instead of using Iter::value_type directly, I'd use:

typename integer = std::iterator_traits<Iter>::value_type

This way, the code can work with (for example) raw pointers, which don't define a value_type member (or any member, for that matter):

int input[] = {144, 4, 8, 28, 12};

int result = gcd(std::begin(input), std::end(input));

Since you only want to work with positive integers anyway, it may be worth considering the possibility of just writing the code to assure that the inputs are some unsigned type (but there's also a fair argument to be made that any time you're doing math, you should probably be using a signed type, and reserve unsigned for things like bit flags, where you're basically just want a 'bag of bits' rather than an actual number).

\$\endgroup\$
3
  • \$\begingroup\$ Thank you for the suggestions! You make a great point that I should use std::iterator_traits<Iter>::value_type so that I can call gcd() with raw pointers. However, I found that this failed to compile with VS2015 due to an ambiguous function call. I tossed the modified code onto cpp.sh and it did compile with its GCC compiler. I tried googling a bit and it seems that VS2015 might have some parsing problems. Do you happen to know of a workaround? If not, no worries since that's outside the scope of this question. \$\endgroup\$
    – Null
    Feb 19, 2016 at 17:09
  • \$\begingroup\$ As for using std::accumulate, I agree that it's a much simpler way to implement GCD for > 2 integers and I hadn't realized that before. I think it makes sense to keep the iterator-based gcd() just to have it check for valid inputs and call std::accumulate internally. Again, VS2015 seems to struggle with an ambiguous function call when I use std::accumulate with gcd<integer> as the binary op function -- but I think this has to do with the fact that I have to use typename integer = typename Iter::value_type in order for VS2015 to compile it. \$\endgroup\$
    – Null
    Feb 19, 2016 at 17:12
  • \$\begingroup\$ @Null: I'm not sure exactly why VS 2015 is rejecting the code, but a quick test indicates that if we wrap it in a (basically vacuous) lambda, it compiles fine: std::accumulate(v.begin(), v.end(), 0, [](int a, int b) { return gcd(a, b); }); \$\endgroup\$ Feb 19, 2016 at 18:20
3
\$\begingroup\$

Your algorithm to compute gcd(a, b) by "repeated subtraction"

// Euclid's algorithm
while (b != 0) {
    if (a > b) a -= b;
    else b -= a;
}
return a;

is correct and is the "original" Euclidean algorithm (I am taking this from Wikipedia:Euclidean algorithm). It can be improved considerably by computing the remainder instead:

while (b != 0) {
    auto remainder = a % b;
    a = b;
    b = remainder;
}
return a;

As an example, computing gcd(84, 18) with the original algorithm takes 8 iterations:

 a  b
=====
84 18
66 18
48 18
30 18
12 18
12  6
 6  6
 6  0

and the second version only 4 iterations:

 a  b
=====
84 18
18 12
12  6
 6  0

For gcd(1000, 2) it is 501 iterations vs 2. It is obvious that the required number of iterations in the original (subtraction) method can be arbitrarily large. For the second (remainder) method, it has been proven that (again from the Wikipedia page)

... the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer.

\$\endgroup\$
2
  • \$\begingroup\$ Good point. I spent much more time getting the template part of the code to work properly (i.e. rejecting non-integral types, allowing the use of containers that don't have random-access iterators, etc.) and not much time on the GCD algorithm itself. Thanks and +1! \$\endgroup\$
    – Null
    Feb 18, 2016 at 20:19
  • \$\begingroup\$ You are welcome and thanks. – I am sure you'll get more answers which cover other aspects of your code (like the templates). \$\endgroup\$
    – Martin R
    Feb 18, 2016 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.