% gcd_euclid: C++ implementation of Euclid's algorithm - GCD(m, n)
\nocon
\datethis
@*Euclid's Algorithm - {\tt GCD}.
{\bf Algorithm}({\sl Euclid's Algorithm}). Given two positive integers |m| and |n|, find
their |greatest common devisor|, that is the largest positive integer that evenly
divides both |m| and |n|.
{\bf E0}. [Ensure $|m| \ge |n|$.] If $|m| < |n|$, exchange $|m| \leftrightarrow |n|$.
{\bf E1}. [Find remainder.] Divide |m| by |n| and let |r| be the remainder.
(We will have $0 \le r < n$)
{\bf E2}. [Is it zero?] If r = 0, the algorithm terminates; n is the answer.
{\bf E3}. [Reduce.] Set $|m| \leftarrow |n|$, $|n| \leftarrow |r|$, and go back to step E1.
@ Two standard header files need to be included, |iostream| to read and write from and to
|stdin| and |algorithm| to define the |std::swap()| function.
@<Include Header Files@>=
#include <algorithm>
#include <iostream>
@ A recursive approach to solve GCD problem.
@<GCD of |m| and |n|@>=
long long int gcd_recursive(long long int m,
long long int n)
{
if (m < n)
return gcd_recursive(n, m);
long long int r = m % n;
if (! r)
return n;
return gcd_recursive(n, r);
}
@ And here is the iterative solution to GCD.
@<GCD of ...@>=
@<Include ...@>
long long int gcd_iterative(long long int m,
long long int n)
{
if (m < n)
std::swap(m, n);
long long int r;
do {
r = m % n;
m = n;
n = r;
} while (0 != r);
/* at this point, n and r are always zero, and m
contains the value of last n which is equal to gcd(m, n) */
return m;
}
@*A simple test of the algorithm.
And here is an example of how to use functions (|gcd_recursive| and |gcd_iterative|):
@c
@<Include Header Files@>@/
@<GCD of |m| and |n|@>@/
@<Main Function@>@/
@ @<Main ...@>=
int main()
{
std::cout << std::endl
<< "Enter a positive integer value for M: ";
long long int m;
std::cin >> m;
std::cout << "Enter a positive integer value for N: ";
long long int n;
std::cin >> n;
long long int gcd_r = gcd_recursive(m, n);
long long int gcd_i = gcd_iterative(m, n);
std::cout << std::endl
<< "gcd_recursive(" << m << ", " << n << ") = " << gcd_r
<< std::endl;
std::cout << std::endl
<< "gcd_iterative(" << m << ", " << n << ") = " << gcd_i
<< std::endl;
exit(EXIT_SUCCESS);
}