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

`function gcd(byVal a, byVal b)`

`a = abs(a)`

`b = abs(b)`

`if a = 0 then`

`gcd = b`

`elseif b = 0 then`

`gcd = a`

`elseif a > b then`

`gcd = gcd(b, a mod b)`

`else`

`gcd = gcd(a, b mod a)`

`end if`

`end function`

`function lcm(byVal a, byVal b)`

`a = abs(a)`

`b = abs(b)`

`if a > b then`

`lcm = (b / gcd(a, b)) * a`

`else`

`lcm = (a / gcd(a, b)) * b`

`end if`

`end function`

#### PHP

`function gcd($a, $b)`

`{`

`$a = abs($a);`

`$b = abs($b);`

`if ($a == 0)`

`{`

`return $b;`

`}`

`elseif ($b == 0)`

`{`

`return $a;`

`}`

`elseif ($a > $b)`

`{`

`return gcd($b, $a % $b);`

`}`

`else`

`{`

`return gcd($a, $b % $a);`

`}`

`}`

`function lcm($a, $b)`

`{`

`$a = abs($a);`

`$b = abs($b);`

`if ($a > $b)`

`{`

`return ($b / gcd($a, $b)) * $a;`

`}`

`else`

`{`

`return ($a / gcd($a, $b)) * $b;`

`}`

`}`

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.

## No comments:

Post a Comment