Greatest Common Divisor of two or more integers

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
#include
#include
#include
#include
#include
#include

/** \brief Computes the greatest common divisor of its arguments.
\tparam integer a type for which
std::is_integral
returns true
*/
template ::value> >
integer gcd(integer a, integer b) {
// Make sure arguments are positive since gcd is always positive
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
\tparam integer a type for which
std::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
integer gcd(Iter first, Iter last) {
auto n = std::distance(first, last);

if (n v;
std::set s;
std::list 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 e

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.

StackExchange Code Review Q#120444, answer score: 3