GCD Program help?

Question

Need help understanding a part of a program which is able to find the GCD. can someone explaine the part from int gcd to before int main starts.

#include
using namespace std;

int gcd (int value1, int value2)
{ int r;
while (value2!=0)
{ r = value1% value2;
value1 = value2;
value2 = r; }
return value1; }
int main (int x, int y, int howmany)
{
cout << "\n Finding the GCD in a C++ program";
cout <<"\n Enter how many GCD computations? ";
cin >> howmany;
for (int i = 0; i < howmany; ++i)
{ cout << "\n Enter two integers: ";
cin >> x >> y; // input of teh 2 values
cout << "\n GCD ("<< x << "," << y << ")=" <
}
}

Answer 1

#include
using namespace std;

int gcd (int value1, int value2)
{ int r;
while (value2!=0)
{ r = value1% value2;
value1 = value2;
value2 = r; }
return value1; }

I agree with McFate. What it is doing is making the loop go until value2 is zero. The r is getting the answer to value1 modulo value2. Then, value1 now contains the number in value2. Value2 then contains the remainder (which is what you get when you mod two numbers). You know you have reached the GCD when value2 is 0, because there is no remainder. Since this is your first encounter... this will be your GCD. I believe this is Euclid's Algorithm for finding the GCD.
For example...

value1 = 21
value2 = 18

r = 21 % 18 -> r now contains the number 3
value1 = value2 -> value1 now contains 18
value2 = r -> value2 now contains 3;

r = 18 % 3 -> r now contains the number 0
value1 = value2 -> value1 now contains the number3
value2 = 0 -> value2 now contains 0 so exit loop

return value1 -> which is now 3 and the answer

Answer 2

EDIT: Answerer 2 is spot on - it is Euclid's Algorithm.

Rather than just describe the code, here is a description of how the actual algorithm works and how it ties up with the code, if that is what you want.

You can represent any integer a like this:

a = qb +r (r < b)

where q is the quotient you get when dividing (a/b).
and r is the remainder of the division.
(a , b , q , r all integers.)

In computing terms r = a % b;

So we want to get gcd(a.b).

If a is an exact multiple of b then gcd(a,b) = b
because a divisor of b cannot be greater than b so b is the greatest common divisor.

So go back to a = qb + r

gcd(a, b) is a common divisor of a and b

but a -qb = r

so gcd(a,b) must also be a divisor of r.
gcd(a , b) is a divisor of b so that means
gcd(a,b) is a common divisor of b and r

So gcd(a,b) <= gcd(b , r)

Reverse is true as every divisor of b and r are also divisors of a

So gcd(a,b) = gcd(b, r)

This can be done recursively as b and r are smaller integers than a and b. This will terminate when we have a divisor - i.e no remainder (r=0). When that happens, the GCD will be c in this equation:

gcd(a , b) = ... gcd(c , r) because c will end up as the largest number that divides a , b and r

During the loop we want to go from calculating
gcd(a,b) to gcd(b,r)

so we just set a=b and b=r and that explains

r=value1 % value2
value1 = value2
value2 = r

We need to loop while r !=0 (same as b!=0 now because we set a=b and b=r at end of loop)

That is why the loop is while value2 !=0

Answer 3

int gcd (int value1, int value2)
{ int r;
while (value2!=0)
{ r = value1% value2;
value1 = value2;
value2 = r; }
return value1; }

What this does, is takes the remainder of dividing one number by the other. This must be the GCD, or some multiple of the GCD, and then it uses that (smaller) number and repeats the process.

In this manner it keeps whittling away at the numbers, always keeping the calculation some multiple of the GCD, until the remainder is 0, at which point it has hit the GCD. It's a pretty neat algorithm, actually.

Let's suppose we start out with value1=15 and value2=24:

(1) v1=15, v2=24, r=15%24 = 15
Then v2->v1 (v1=24), and r->v2 (v2=15)
(2) v1=24, v2=15, r=24%15 = 9
Then v2->v1 (v1=15), and r->v2 (v2=9)
(3) v1=15, v2=9, r=15%9 = 6
Then v2->v1 (v1=9), and r->v2 (v2=6)
(4) v1=9, v2=6, r=9%6 = 3
Then v2->v1 (v1=6), and r->v2 (v2=3)
(5) v1=6, v2=3, r=6%3 = 0
Then v2->v1 (v1=3), and r->v2 (v2=0)
Exits the loop because v2=0, and returns 3.

And 3 is the GCD of 15 and 24.