Look for the GCD (greatest common divisor) of more than 2 integers?

Question

I already have a function that finds the GCD of 2 numbers.

function getGCDBetween($a, $b)
{
    while ($b != 0)
    {
        $m = $a % $b;
        $a = $b;
        $b = $m;
    }
    return $a;
}

But now, I would like to extend this function to find the GCD of N points. Any suggestion ?

Answer 1

There is a more elegant way to do this :

// Recursive function to compute gcd (euclidian method)
function gcd ($a, $b) {
    return $b ? gcd($b, $a % $b) : $a;
}
// Then reduce any list of integer
echo array_reduce(array(42, 56, 28), 'gcd'); // === 14

If you want to work with floating points, use approximation :

function fgcd ($a, $b) {
    return $b > .01 ? fgcd($b, fmod($a, $b)) : $a; // using fmod
}
echo array_reduce(array(2.468, 3.7, 6.1699), 'fgcd'); // ~= 1.232

You can use a closure in PHP 5.3 :

$gcd = function ($a, $b) use (&$gcd) { return $b ? $gcd($b, $a % $b) : $a; };

Answer 2

Had to do a bit of digging, but this is what I found.

The gcd of three numbers can be computed as gcd(a, b, c) = gcd(gcd(a, b), c), or in some different way by applying commutativity and associativity. This can be extended to any number of numbers.

You could use something like the following:

function multiGCD($nums)
{
    $gcd = getGCDBetween($nums[0], $nums[1]);

    for ($i = 2; $i < count($nums); $i++) { $gcd = getGCDBetween($gcd, $nums[$i]); }

    return $gcd;
}

Answer 3

Take the GCD of numbers 1 and 2, and then the GCD of that and number 3, and so on.