PHP - Manual: gmp_gcd

2024-11-14

gmp_gcd

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

gmp_gcd — Calculate GCD

说明

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.

参数

num1: GMP 对象或 int ，或数字string。
num2: GMP 对象或 int ，或数字string。

返回值

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

范例

示例 #1 gmp_gcd() example


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

以上例程会输出：

参见

gmp_lcm() - Calculate LCM

add a note

User Contributed Notes 8 notes

down

bigkm1 at gmail dot com ¶

15 years ago


here is an elegant recursive solution
<?php    

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

?>

down

sean__remove__ at eternalrise_r_emove__ dot com ¶

13 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));
}

?>

down

delboy1978uk at gmail dot com ¶

4 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

down

limas at kultur-online dot at ¶

14 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);
}

down

-1

me at abiusx dot com ¶

2 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.

down

Ludwig Heymbeeck ¶

19 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;
}

down

-1

scr02001 at student dot mdh dot se ¶

18 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;
}

down

-5

x-empt-php dot net at ispep dot cx ¶

19 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

官方地址：https://www.php.net/manual/en/function.gmp-gcd.php

有任何技术问题请点击这里网站运营推广招聘

IT PHP 编程语言 Linux 开发编程科技 Elasticsearch HTML/CSS/XML 网络 JAVA NoSQL 数据库面试 C/C++ Golang Git 算法操作系统正则表达式 Redis 互联网 MySql JavaScript 运维软件国际架构设计 Mac OS TCP/IP Excel Vim Windows Socket Oracle VR MongoDB Python 运营 MemCache 商业硬件电子娱乐设计 nginx 摄影游戏 WordPress HTTP 团建数码电器

php7 安装fileinfo扩展 preg_split — 通过一个正则表达式分隔字符串 php位值,解决 PHP 中 usort 在值相同时改变原始位置的问题 [PHP] inet_pton/inet_ntop IP地址转换函数 array_multisort() 多字段排序 PHPMailer设置utf8 PHPMailer字符集CharSet ADORecordSet对象 adodb手册 PHP 8.1 [鸟哥]PHP_INT_MIN 和 -9223372036854775808 opcache预加载 Composer的Packagist资源 mysql面试题 [鸟哥]PHP FFI详解 - 一种全新的PHP扩展方式 PHP7添加redis扩展 PHP mkdir()写出来的权限与mode值不符合 Packagist / Composer 中国全量镜像 PHP注释规范支持php7的性能采集扩展 adodb连接mysql多个数据库的问题

略微加速

PHP官方手册 - 互联网笔记

gmp_gcd

说明

参数

返回值

范例

参见

User Contributed Notes 8 notes