• 首页
  • vue
  • TypeScript
  • JavaScript
  • scss
  • css3
  • html5
  • php
  • MySQL
  • redis
  • jQuery
  • gmp_gcd()

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

    Calculate GCD

    说明

    gmp_gcd(GMP$a, GMP$b): GMP

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

    参数

    $a

    可以是一个 GMP数据resouce,或一个可以转换为数值的字符串。

    $b

    可以是一个 GMP数据resouce,或一个可以转换为数值的字符串。

    返回值

    A positive GMP number that divides into both$aand$b.

    范例

    gmp_gcd() example

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

    以上例程会输出:

    3
    

    参见

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

    上篇:gmp_fact()

    下篇:gmp_gcdext()