int gcd(int a, int b) // a, b > 0
{
while ( a != b )
{
if ( a < b )
b -= a;
else
a -= b;
}
return a;
}
void exchange(int &x, int &y)
{
int tmp = x;
x = y;
y = tmp;
}
int gcd2(int a, int b) // a, b > 0
{
while ( a != b )
{
if ( a > b ) exchange(a,b);
b -= a;
}
return a;
}
int gcd3(int a, int b) // a, b > 0
{
while ( a != b )
{
if ( a > b ) exchange(a,b);
for ( int c = a; c < b; c *= 2 )
b -= c;
}
return a;
}
// Why it works
if g = gcd(a,b) then there are integers m and n such that
a = g*m and b = g*n. g, m, and n are initially unknown but
they exist. Also, gcd(m,n) = 1; otherwise there would be
a larger common factor than g.
the invariant for each version is
gcd(a,b) = g = gcd(original a, original b)
and a, b > 0. Since gcd(x,x)=x for any x,
the invariant and the loop termination condition
together give us a=g.
subtracting k*a from b, for some integer k, is equivalent
to subtracting k*m from n. In the first two versions k
is always 1; in the second version it can be any non-negative
power of two.
Because (m+n) decreases by at least one on each iteration
and a,b > 0 is invariant, the loop must terminate.
It remains to be shown that gcd(a-k*b,b) = gcd(a,b). This is
an elementary theorem in number theory, the proof of which
I will not go into here. With that theorem in hand, however,
it is clear that the invariant is preserved by the loop body.
invariant true before loop +
invariant and loop condition => invariant after body +
invariant and !loop condition => correct answer
is the proof template for a while loop.
// Why version 3 is faster
Assume initially m >> n, say m ~ 1000*n. Then in the
first two versions around 1000 subtractions are required
before the algorithm gets close to finished.
In the third version, however, only about log-base-2 (1000) ~ 10
iterations of the inner loop are required to knock the larger
number down to size.
Therefore, as the ratio m/n (assuming a>b) gets large, the
ratio of steps used in version three to steps used in the
simpler algorithm goes to 0:
limit x->+inf (log x/x) = 0 ( L'Hopital's rule )
// Suggested exercises:
1. Performance
Write a main that calls versions 2 and 3 of gcd for parameters
(1,1), (1,10), (1,100), (1,1000)
Instrument the code of each version (as if it were a simulation
program) to report how many times the subtraction step is performed.
Have main print a table of the results, with a column for the
ratio of operations and the predicted ratio. Compare the result with
the theory.
2. Correctness
write a main that tests all three versions of gcd.
Use a small table of prime numbers (easy to find on the net)
and each time through the loop choose two of them randomly
(but not equal) and a random g. Then gcd(g*a,g*b)==g is
easy to verify. Limit the range of numbers so that g*a is
not more than about 10^8 to avoid integer overflow problems.
Insert an error into one of the functions and verify that
your test detects it.