|
|
|
|
Bookmark this on Delicious
Share on Facebook
 Slashdot It!
Digg  gmp_gcd
Calculate GCD
(PHP 4 >= 4.0.4, PHP 5)
Example 791. gmp_gcd() example<?phpThe above example will output: 3Code Examples / Notes » gmp_gcdludwig 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_add 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 |
