gmp_gcd

here is an elegant recursive solution<?php    function gcd($a,$b) {    return ($a % $b) ? gcd($b,$a % $b) : $b;}?>

Here's my solution for getting the GCD of several numbers.<?php/* * function gcd() *  * returns greatest common divisor * between two numbers * tested against gmp_gcd() */function gcd($a, $b){    if ($a == 0 || $b == 0)        return abs( max(abs($a), abs($b)) );            $r = $a % $b;    return ($r != 0) ?        gcd($b, $r) :        abs($b);}/* * function gcd_array() *  * gets greatest common divisor among * an array of numbers */function gcd_array($array, $a = 0){    $b = array_pop($array);    return ($b === null) ?        (int)$a :        gcd_array($array, gcd($a, $b));}?>

I wanted this functionality without having to install the extension.So here's a script I wrote to find out the greatest common denominator:<?php// Our fraction, 3/12, could be written better$numerator = 3;$denominator = 12;/** * @param int $num * @return array The common factors of $num */function getFactors($num) {    $factors = [];    // get factors of the numerator    for ($x = 1; $x <= $num; $x ++) {        if ($num % $x == 0) {            $factors[] = $x;        }    }    return $factors;}/** * @param int $x * @param int $y */function getGreatestCommonDenominator($x, $y){    // first get the common denominators of both numerator and denominator    $factorsX = getFactors($x);    $factorsY = getFactors($y);        // common denominators will be in both arrays, so get the intersect    $commonDenominators = array_intersect($factorsX, $factorsY);        // greatest common denominator is the highest number (last in the array)    $gcd = array_pop($commonDenominators);    return $gcd;}// divide the numerator and denomiator by the gcd to get our refactored fraction$gcd = getGreatestCommonDenominator($numerator, $denominator);echo ($numerator / $gcd) .'/'. ($denominator / $gcd); // we can use divide (/) because we know result is an int :-)Which you can see running here https://3v4l.org/uTucY

The previous function returns just 1 under php 5.2.4  but the following seems to work (m>0,n>0):function gcd($m,$n){    $_m=$m;$r=1;    if($m<$n){$t=$m;$m=$n;$n=$t;}        while($r)    {        $r=(floor($m/$n)*$n)-$m;              $_n=$n;$n=$r;$m=$_m;    }         return abs($_n);}

function gcd($a,$b){    return $b ? gcd($b, $a%$b) : $a;}This is pretty fast and short, also easy to remember. If $b is zero, return a, otherwise swap and mod.

The following function is more accurate:function GCD($num1, $num2) {/* finds the greatest common factor between two numbers */   while ($num2 != 0){     $t = $num1 % $num2;     $num1 = $num2;     $num2 = $t;   }   return $num1;}

If you do not consier a or b as possible negative numbers, a GCD funktion may return a negative GCD, wich is NOT a greatest common divisor, therefore a funktion like this may be better. This considers the simplyfying of (-3)-(-6) where gcd on -3 and -6 would result in 3, not -3 as with the other function. (-3)-(-6) is (-1)-(-2) NOT (1)-(2)function eGCD($a,$b){  if($a < 0)         $a=0-$a;  if($b < 0 )        $b=0-$b;  if($a == 0 || $b == 0)    return 1;  if($a == $b)              return a;   do{  $rest=(int) $a % $b;  $a=$b; $b=$rest;  }while($rest >0);return $a;}

No need to compile gmp functions in just for the GCD function...  use this one instead:function GCD($num1, $num2) { /* finds the greatest common factor between two numbers */    if ($num1 < $num2) {        $t = $num1;        $num1 = $num2;        $num2 = $t;    }    while ($t = ($num1 % $num2) != 0) {        $num1 = $num2;        $num2 = $t;    }    return $num2;}