Delicious Bookmark this on Delicious Share on Facebook SlashdotSlashdot It! Digg! Digg



PHP : Function Reference : GMP Functions : gmp_gcd

gmp_gcd

Calculate GCD (PHP 4 >= 4.0.4, PHP 5)
resource gmp_gcd ( resource a, resource b )

Example 791. gmp_gcd() example

<?php
$gcd
= gmp_gcd("12", "21");
echo
gmp_strval($gcd) . "\n";
?>

The above example will output:

3

Code Examples / Notes » gmp_gcd

ludwig heymbeeck

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

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;
}


scr02001

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;
}


bigkm1

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


Change Language


Follow Navioo On Twitter
gmp_abs
gmp_add
gmp_and
gmp_clrbit
gmp_cmp
gmp_com
gmp_div_q
gmp_div_qr
gmp_div_r
gmp_div
gmp_divexact
gmp_fact
gmp_gcd
gmp_gcdext
gmp_hamdist
gmp_init
gmp_intval
gmp_invert
gmp_jacobi
gmp_legendre
gmp_mod
gmp_mul
gmp_neg
gmp_nextprime
gmp_or
gmp_perfect_square
gmp_popcount
gmp_pow
gmp_powm
gmp_prob_prime
gmp_random
gmp_scan0
gmp_scan1
gmp_setbit
gmp_sign
gmp_sqrt
gmp_sqrtrem
gmp_strval
gmp_sub
gmp_testbit
gmp_xor
eXTReMe Tracker