Euclid's Algorithm

Euclid's algorithm is one of the oldest, known by ancient Greeks like Aristotle. You might remember it from elementary school when you had to find things like greatest common factor/divisor and least common multiple. Greatest common factor/divisor allowed you to reduce fractions like 4/12 to 1/3. Least common multiple allowed you to add and subtract fractions that had different denominators.

There is more than one way to implement this algorithm. The original involved iterative subtraction. This was later improved upon with iterative modulo division. Another method, the one I'll be using here, is recursion.

ASP

1. function gcd(byVal a, byVal b)
2.     a = abs(a)
3.     b = abs(b)
5.     if a = 0 then
6.         gcd = b
7.     elseif b = 0 then
8.         gcd = a
9.     elseif a > b then
10.         gcd = gcd(b, a mod b)
11.     else
12.         gcd = gcd(a, b mod a)
13.     end if
14. end function
16. function lcm(byVal a, byVal b)
17.     a = abs(a)
18.     b = abs(b)
20.     if a > b then
21.         lcm = (b / gcd(a, b)) * a
22.     else
23.         lcm = (a / gcd(a, b)) * b
24.     end if
25. end function

PHP

1. function gcd($a, $b)
2. {
3.     $a = abs($a);
4.     $b = abs($b);
6.     if ($a == 0)
7.     {
8.         return $b;
9.     }
10.     elseif ($b == 0)
11.     {
12.         return $a;
13.     }
14.     elseif ($a > $b)
15.     {
16.         return gcd($b, $a % $b);
17.     }
18.     else
19.     {
20.         return gcd($a, $b % $a);
21.     }
22. }
24. function lcm($a, $b)
25. {
26.     $a = abs($a);
27.     $b = abs($b);
29.     if ($a > $b)
30.     {
31.         return ($b / gcd($a, $b)) * $a;
32.     }
33.     else
34.     {
35.         return ($a / gcd($a, $b)) * $b;
36.     }
37. }

Euclid's algorithm is not always the fastest, but it is the simplest. A better algorithm was devised by 20th century mathematician Dick Lehmer. Another 20th century mathematician, Josef Stein, devised a specialized algorithm for computers which uses bit shifting. Note, however, that the performance improvement of these more modern algorithms varies depending on the CPU and size of the numbers involved. In some cases, Euclid is actually faster.

• ASP implementation on Snipplr
• PHP implementation on Snipplr