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
参见
gmp_lcm()
Calculate LCM
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; }