Posted By

Scooter on 05/24/08


Tagged

math


Versions (?)

Euclid's Algorithm


 / Published in: PHP
 

URL: http://reusablecode.blogspot.com/2008/05/euclids-algorithm.html

  1. <?php
  2. /*
  3.   PHP Mathematics Library - Euclid's Algorithm
  4.  
  5.   Copyright (c) 2008, reusablecode.blogspot.com; some rights reserved.
  6.  
  7.   This work is licensed under the Creative Commons Attribution License. To view
  8.   a copy of this license, visit http://creativecommons.org/licenses/by/3.0/ or
  9.   send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California
  10.   94305, USA.
  11.   */
  12.  
  13. // Determine the greatest common divisor of two numbers using Euclid's algorithm.
  14. function gcd($a, $b)
  15. {
  16. $a = abs($a);
  17. $b = abs($b);
  18.  
  19. if ($a == 0)
  20. {
  21. return $b;
  22. }
  23. elseif ($b == 0)
  24. {
  25. return $a;
  26. }
  27. elseif ($a > $b)
  28. {
  29. return gcd($b, $a % $b);
  30. }
  31. else
  32. {
  33. return gcd($a, $b % $a);
  34. }
  35. }
  36.  
  37. // Determine the least common multiple of two numbers using Euclid's algorithm.
  38. function lcm($a, $b)
  39. {
  40. $a = abs($a);
  41. $b = abs($b);
  42.  
  43. if ($a > $b)
  44. {
  45. return ($b / gcd($a, $b)) * $a;
  46. }
  47. else
  48. {
  49. return ($a / gcd($a, $b)) * $b;
  50. }
  51. }
  52. ?>

Report this snippet  

You need to login to post a comment.