gmp_fact
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));
}
?>
gmp_gcd
(PHP 4 >= 4.0.4, PHP 5)
gmp_gcd — Calcule le GCD
Description
resource gmp_gcd
( resource
$a
, resource $b
)
Calcule le PGCD (plus grand commun diviseur) de a
et b. Le résultat est toujours positif, même si
l'un des deux (ou les deux) nombres est négatif.
Liste de paramètres
-
a -
Il peut être soit une ressource GMP, soit une chaîne numérique qu'il est possible de convertir plus tard en un nombre.
-
b -
Il peut être soit une ressource GMP, soit une chaîne numérique qu'il est possible de convertir plus tard en un nombre.
Valeurs de retour
Un nombre positif GMP qui se divise avec
a et b.
Exemples
Exemple #1 Exemple avec gmp_gcd()
<?php
$gcd = gmp_gcd("12", "21");
echo gmp_strval($gcd) . "\n";
?>
L'exemple ci-dessus va afficher :
3
add a note
User Contributed Notes
gmp_gcd
sean__remove__ at eternalrise_r_emove__ dot com
10-Nov-2008 07:50
jim dot mayes at gmail dot com
03-Apr-2008 01:53
Try...
function gcd($a, $b){
$b = ( $a == 0 )? 0 : $b;
return ( $a % $b )? gcd($b, abs($a - $b)) : $b;
}
always returns positive number even if one or both numbers are negative (as per the gmp_gcd function)
order agnostic, larger number can be $b or $a doesn't matter
also, other examples here were failing when one of the numbers was 0
limas at kultur-online dot at
01-Dec-2007 10:44
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);
}
bigkm1 at gmail dot com
25-Aug-2006 09:33
here is an elegant recursive solution
<?php
function gcd($a,$b) {
return ($a % $b) ? gcd($b,$a % $b) : $b;
}
?>
scr02001 at student dot mdh dot se
16-Aug-2003 06:58
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;
}
Ludwig Heymbeeck
12-Jan-2003 10:33
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;
}
x-empt-php dot net at ispep dot cx
06-Jul-2002 11:16
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;
}