Saturday, October 20, 2012

Euclid's Algorithm (elaborated explanation)


Euclid's algorithm for finding the greatest common divisor of two integers is perhaps the oldest nontrivial algorithm that has survived to the present day.
In mathematics the Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers. Also, this method is known as the greatest common factor (GCF) or highest common factor (HCF).

Theorem
Let a, b, q and  r be integers with b > 0 and 0 <= r < b such that a = bq + r .
Then gcd(a, b) = gcd(b, r)

Before we continue, I will demonstrate how it works. Assume we have two integer numbers, 240 and 560 and we need to find such a number which will be the biggest one, which will divide both of 240 and 560.

According to Euclid's algorithm:
a = 240, b = 560.  We must find such r and q that will satisfy 240 = 560*q + r.
Lets divide 240 mod 560. = > q = 0, r = 240.
That is the remainder of such division is 240, while the integer part q equals to zero.

Note: 240 mod 560 is called 240 modulo 560. Result of such operation is the remainder of the division. Additional example of modulo operation is 11 mod 2 = 1, because 11 = 2*5 + 1. In our case q = 5, r = 1.

If we continue, while b not equals to zero, we receive the following:
gcd(240,560)  = > 240 mod 560 = 240
gcd(560,240)  =>  560 mod 240 = 80
gcd(240,80)    =>  240 mod 80 = 0.
gcd(80, 0). Here we got b equals to 0. SO the greatest common divisor of 240 and 560 is 80.

This algorithm can be implemented recursively or iteratively.

Recursively:
gcd(a,b)
{
     if (b == 0)     return a;
    else
         return gcd(b, a mod b);
}
Iteratively (version 1):
gcd(a,b)
{
    while (b != 0)
     {
         t = b;
         b = a mod b;
         a = t;
     }
    return a;
}
Iteratively (version 2):
gcd(a,b)
{
    if (a == 0)   return b;
    while  (b != 0)
     {
           if (a>b)
              a = a - b;
          else
             b = b - a;
     }
   return a;
}
Example:
gcd(1989,867)

1989 - 867 = 1122  -->    gcd(1122,867)
1122 - 867 = 255    -->    gcd(255,867)
867 - 255 = 612      -->    gcd(255,612)
612 - 255 = 357      -->    gcd(255,357)
357 - 255 = 102      -->    gcd(255,102)
153 - 102 = 51        -->    gcd(51,102)
102 - 51 = 51          -->    gcd(51,51)
51 - 51 = 0.
Result is 51.

Another way to calculate the greatest common divisor is based on the following theorem.
Note: least common multiplier

Example:
gcd(240,560)  
lcm(240,560)

or
if      gcd(240,560) = 80   ==> lcm(240,560)= 240*560/80 = 1680
or
knowing lcm(240,560) ==> gcd(240,560)=240*560/1680 = 80