gmp_gcd
(PHP 4 >= 4.0.4, PHP 5)
gmp_gcd — Вычисление наибольшего общего делителя
Описание
resource gmp_gcd
( resource
$a
, resource $b
)
Вычисляет наибольший общий делитель чисел a и
b. Результат всегда положителен, даже если одно
из чисел, или оба, отрицательные.
Список параметров
-
a -
Может быть как числом GMP, так и строкой, при условии, что ее значение можно конвертировать в число.
-
b -
Может быть как числом GMP, так и строкой, при условии, что ее значение можно конвертировать в число.
Возвращаемые значения
Положительный НОД чисел
a и b.
Примеры
Пример #1 Пример использования gmp_gcd()
<?php
$gcd = gmp_gcd("12", "21");
echo gmp_strval($gcd) . "\n";
?>
Результат выполнения данного примера:
3
- PHP Руководство
- Функции по категориям
- Индекс функций
- Справочник функций
- Математические расширения
- GNU Вычисления с увеличенной точностью
- 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_export
- gmp_fact
- gmp_gcd
- gmp_gcdext
- gmp_hamdist
- gmp_import
- 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_bits
- gmp_random_range
- gmp_random_seed
- gmp_random
- gmp_root
- gmp_rootrem
- gmp_scan0
- gmp_scan1
- gmp_setbit
- gmp_sign
- gmp_sqrt
- gmp_sqrtrem
- gmp_strval
- gmp_sub
- gmp_testbit
- gmp_xor
Коментарии
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;
}
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;
}
here is an elegant recursive solution
<?php
function gcd($a,$b) {
return ($a % $b) ? gcd($b,$a % $b) : $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);
}
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));
}
?>
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
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.