Greatest Common Divisor / Least Common Multiple

[CheezPuppett]

Hello all,

are there PHP functions for determining the greatest common divisor or least common multiple of an array of numbers? I've searched, but I can't seem to find anything. Any help is greatly appreciated.

Thanks,
cheeze

[bernouli]

what is it for a function?
what does this function?
maybe with a simple own made function can help you

[CheezPuppett]

Yes I need functions to determine the greatest common divisor and least common multiples of an array of integers. If the GCD function is passed an array of numbers, say 20,30,100, it returns 10, since 10 is the greatest common denominator. Does PHP have a built-in function for such a task?

[bernouli]

try this function, it can be used unfortunately only for two variables

function gcd($a,$b) {
 $x=$a;
 $y=$b;
while($x!=$y){
	if($x > $y) $x=$x-$y;
	else $y=$y-$x;
}
return y;
}

[CheezPuppett]

Thanks, but I had a function which worked on two numbers, and it went like this:

function GCD($x, $y) {
	while($y != 0) {
		$r = $x % $y;
		$x = $y;
		$y = $r;
	}
	return abs($x);
}

But I'd like to be able to pass the function an array of values, rather than two, and that's where I'm having problems.

Thanks.

[mrmufin]

I had a similar need for an application I worked on. Here's what I used; if anybody has any better solutions, I'd sure like to know:

function GetGCD($vars) {
	// Ascertain that $vars is an array:
	if(is_array($vars)) {
		// Count the array elements:
		$n = count($vars);
		// If there's just one array element, then it must be the GCD. Return:
		if($n == 1) {
			return $vars[0];
		}
		// Loop through the array elements:
		for($i = 0; $i < $n; $i++) {
			// Set up the current comparison values. If there's not a 'temporary'
			// GCD yet, we're on the first element:
			if(!$a) {
				$a = $vars[$i];
			}
			$b = $vars[$i + 1];
			while($b != 0) {
				$r = $a % $b;
				$a = $b;
				$b = $r;
			}
			$a = abs($a);
		}
		return $a;
	}
}

echo 'GCD: ' . GetGCD(array(52,24,36,48)) . '<br />';

Now I'll see if I can dig up my GetLCM() function outta the archives; if I recall correctly, it used the GetGCD() function...

Have fun...

[mrmufin]

And the GetLCM() function; which relies on the GetGCD() function:

function GetLCM($vars) {
        if(is_array($vars) && function_exists(GetGCD)) {
                $n = count($vars);
                if($n == 1) {
                        return $vars[0];
                }
                for($i = 0; $i < $n; $i++) {
                        if(!$a) {
                                $a = $vars[$i];
                        }
                        $b = $vars[$i + 1];
                        if($b != 0) {
                                $arr = array($a, $b);
                                $a = abs($a * $b / GetGCD($arr));
                        }
                }
                return $a;
        }
}

As I said before, if anyone has a better method of finding these values, I would sure like to know...