From: [EMAIL PROTECTED] Operating system: Solaris 8 PHP version: 4.3.0 PHP Bug Type: *Math Functions Bug description: GMP lib gmp_gcdext() gives incorrect results
I was testing some of the gmp functions and found that gmp_gcdext() does not behave as the prototype and description claim, or I am not understanding what exactly is the correct behavior of the function. Based on the decsription in the documentation for the gmp library, and the gmp_gcdext() function in the PHP manual, the code: $r = gmp_gcdext($a, $b); should return an array $r w/ elements g, s, and t, such that: $a*$s + $b*$t = $g [Eq. 1] where: $g = gmp_gcd($a, b); Eq. [1] is similar to what is know as a "Diophantine Equation". See http://mathworld.wolfram.com/DiophantineEquation.html for more information, and an example. Using: $a = gmp_init(1027); and $b = gmp_init(712); the function gmp_gcdext() fails to produce the correct results. In fact, using almost any set of values it just gives non-sensical results. The following code: echo "Diophantine equation: 1027*s + 712*t = 1\n"; echo "Solution: s = -165, t = 238\n"; $res = -165*1027 + 238*712; echo "Check: 1027*(-165) + 238*712 = $res\n\n"; $a = gmp_init(1027); $b = gmp_init(712); echo 'a = '.gmp_strval($a)."\n"; echo 'b = '.gmp_strval($b)."\n"; $g = gmp_gcd($a, $b); echo 'g = gcd(a,b) = '.gmp_strval($g)."\n"; echo "\na = ".gmp_strval($a)."\n"; echo 'b = '.gmp_strval($b)."\n"; $r = gmp_gcdext($a, $b); var_dump($r); echo 'g = '.gmp_strval($r['g'])."\n"; echo 's = '.gmp_strval($r['s'])."\n"; echo 't = '.gmp_strval($r['t'])."\n"; $test = gmp_add(gmp_mul($a, $r['s']), gmp_mul($b, $r['t'])); echo 'a*s + b*t = '.gmp_strval($test)."\n"; Produces the output: a = 1027 b = 712 g = gcd(a,b) = 1 a = 1027 b = 712 array(3) { ["g"]=> resource(7) of type (GMP integer) ["s"]=> resource(8) of type (GMP integer) ["t"]=> resource(9) of type (GMP integer) } g = 1027 s = 1 t = 0 a*s + b*t = 1027 Which is clearly wrong. If you look at the URL mentioned above, the solution to: 1027x + 712y = 1 is: x = -165, y = 238 When I used 12 and 21 for $a and $b respectively, I got: a = 12 b = 21 g = gcd(a,b) = 3 a = 12 b = 21 array(3) { ["g"]=> resource(7) of type (GMP integer) ["s"]=> resource(8) of type (GMP integer) ["t"]=> resource(9) of type (GMP integer) } g = 12 s = 1 t = 0 a*s + b*t = 12 And when I used 21 and 12 for $a and $b respectively: a = 21 b = 12 g = gcd(a,b) = 3 a = 21 b = 12 array(3) { ["g"]=> resource(7) of type (GMP integer) ["s"]=> resource(8) of type (GMP integer) ["t"]=> resource(9) of type (GMP integer) } g = 21 s = 1 t = 0 a*s + b*t = 21 The PHP wrapping code seems to be OK (from today's CVS, 2003-01-08), and I gave up tracking down the wrapping macros and such in the gmp lib code, where the actual bug might reside. Will send an email to the gmp maintainers too. I am using gmp 4.1.2, and testing w/ PHP 4.3.0 CLI, under Solaris 8. -- Edit bug report at http://bugs.php.net/?id=21534&edit=1 -- Try a CVS snapshot: http://bugs.php.net/fix.php?id=21534&r=trysnapshot Fixed in CVS: http://bugs.php.net/fix.php?id=21534&r=fixedcvs Fixed in release: http://bugs.php.net/fix.php?id=21534&r=alreadyfixed Need backtrace: http://bugs.php.net/fix.php?id=21534&r=needtrace Try newer version: http://bugs.php.net/fix.php?id=21534&r=oldversion Not developer issue: http://bugs.php.net/fix.php?id=21534&r=support Expected behavior: http://bugs.php.net/fix.php?id=21534&r=notwrong Not enough info: http://bugs.php.net/fix.php?id=21534&r=notenoughinfo Submitted twice: http://bugs.php.net/fix.php?id=21534&r=submittedtwice register_globals: http://bugs.php.net/fix.php?id=21534&r=globals PHP 3 support discontinued: http://bugs.php.net/fix.php?id=21534&r=php3 Daylight Savings: http://bugs.php.net/fix.php?id=21534&r=dst IIS Stability: http://bugs.php.net/fix.php?id=21534&r=isapi Install GNU Sed: http://bugs.php.net/fix.php?id=21534&r=gnused