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