Edit Report a Bug

    gmp_gcd

    (PHP 4 >= 4.0.4, PHP 5, PHP 7, PHP 8)

    gmp_gcd — Calculate GCD

    Description

    gmp_gcd(GMP|int|string $num1, GMP|int|string $num2): GMP

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

    Parameters

    num1

    A GMP object, an int or a numeric string.

    num2

    A GMP object, an int or a numeric string.

    Return Values

    A positive GMP number that divides into both num1 and num2.

    Examples

    Example #1 gmp_gcd() example

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

    The above example will output:

    3

    See Also

    add a note add a note

    User Contributed Notes 8 notes

    up
    11
    bigkm1 at gmail dot com
    18 years ago
    here is an elegant recursive solution
    <?php   

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

    ?>
    up
    2
    sean__remove__ at eternalrise_r_emove__ dot com
    16 years ago
    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));
    }

    ?>
    up
    0
    delboy1978uk at gmail dot com
    7 years ago
    I wanted this functionality without having to install the extension.

    So here's a script I wrote to find out the greatest common denominator:

    <?php

    // Our fraction, 3/12, could be written better
    $numerator = 3;
    $denominator = 12;

    /**
    * @param int $num
    * @return array The common factors of $num
    */
    function getFactors($num)
    {
            $factors = [];
            // get factors of the numerator
            for ($x = 1; $x <= $num; $x ++) {
            if (    $num % $x == 0) {
                    $factors[] = $x;
            }
        }
        return     $factors;
    }

    /**
    * @param int $x
    * @param int $y
    */
    function getGreatestCommonDenominator($x, $y)
    {
            // first get the common denominators of both numerator and denominator
            $factorsX = getFactors($x);
            $factorsY = getFactors($y);
       
            // common denominators will be in both arrays, so get the intersect
            $commonDenominators = array_intersect($factorsX, $factorsY);
       
            // greatest common denominator is the highest number (last in the array)
            $gcd = array_pop($commonDenominators);
        return     $gcd;
    }

    // divide the numerator and denomiator by the gcd to get our refactored fraction
    $gcd = getGreatestCommonDenominator($numerator, $denominator);
    echo (    $numerator / $gcd) .'/'. ($denominator / $gcd); // we can use divide (/) because we know result is an int :-)

    Which you can see running here https://3v4l.org/uTucY
    up
    0
    limas at kultur-online dot at
    17 years ago
    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);
    }
    up
    -1
    me at abiusx dot com
    4 years ago
    function gcd($a,$b)
    {
        return $b ? gcd($b, $a%$b) : $a;
    }

    This is pretty fast and short, also easy to remember. If $b is zero, return a, otherwise swap and mod.
    up
    0
    Ludwig Heymbeeck
    21 years ago
    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;
    }
    up
    -1
    scr02001 at student dot mdh dot se
    21 years ago
    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;
    }
    up
    -5
    x-empt-php dot net at ispep dot cx
    22 years ago
    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;
    }
    add a note add a note
    To Top