Ajax Javascript HTML CSS PHP C#
Bookmark this on Delicious Share on Facebook Slashdot It! Digg

PHP : Function Reference : GMP Functions : gmp_gcd

# gmp_gcd

## Calculate GCD (PHP 4 >= 4.0.4, PHP 5) resource gmp_gcd ( resource a, resource b )

### Example 791. gmp_gcd() example

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

The above example will output:

3

## Code Examples / Notes » gmp_gcd

ludwig heymbeeck

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

x-empt-php dot net

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

scr02001

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

bigkm1

here is an elegant recursive solution
<?php
function gcd(\$a,\$b) {
return (\$a % \$b) ? gcd(\$b,\$a % \$b) : \$b;
}
?>

### Change Language

gmp_abs
gmp_and
gmp_clrbit
gmp_cmp
gmp_com
gmp_div_q
gmp_div_qr
gmp_div_r
gmp_div
gmp_divexact
gmp_fact
gmp_gcd
gmp_gcdext
gmp_hamdist
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
gmp_scan0
gmp_scan1
gmp_setbit
gmp_sign
gmp_sqrt
gmp_sqrtrem
gmp_strval
gmp_sub
gmp_testbit
gmp_xor