PHP Doku:: Calculate GCD - function.gmp-gcd.html

Verlauf / Chronik / History: (1) anzeigen

Sie sind hier:
Doku-StartseitePHP-HandbuchFunktionsreferenzMathematische ErweiterungenGNU Multiple PrecisionGMP Funktionengmp_gcd

Ein Service von Reinhard Neidl - Webprogrammierung.

GMP Funktionen

<<gmp_fact

gmp_gcdext>>

gmp_gcd

(PHP 4 >= 4.0.4, PHP 5)

gmp_gcdCalculate GCD

Beschreibung

resource gmp_gcd ( resource $a , resource $b )

Calculate greatest common divisor of a and b. The result is always positive even if either of, or both, input operands are negative.

Parameter-Liste

a

Dies kann entweder eine resource für einen GMP-Wert sein oder ein numerischer String, wenn es möglich ist, diesen in einen GMP-Wert umzuwandeln.

b

Dies kann entweder eine resource für einen GMP-Wert sein oder ein numerischer String, wenn es möglich ist, diesen in einen GMP-Wert umzuwandeln.

Rückgabewerte

A positive GMP number that divides into both a and b.

Beispiele

Beispiel #1 gmp_gcd() example

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

Das oben gezeigte Beispiel erzeugt folgende Ausgabe:

3


7 BenutzerBeiträge:
- Beiträge aktualisieren...
sean__remove__ at eternalrise_r_emove__ dot com
11.11.2008 4:50
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));
}

?>
jim dot mayes at gmail dot com
3.04.2008 23: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
1.12.2007 19: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
26.08.2006 6: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.08.2003 15: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.01.2003 19: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
7.07.2002 8: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;
}



PHP Powered Diese Seite bei php.net
The PHP manual text and comments are covered by the Creative Commons Attribution 3.0 License © the PHP Documentation Group - Impressum - mail("TO:Reinhard Neidl",...)