#21534 [Opn]: GMP lib gmp_gcdext() gives incorrect results

ID: 21534 Updated by: jmcastagnetto@php.net Reported By: jmcastagnetto@php.net Status: Open Bug Type: *Math Functions Operating System: Solaris 8 PHP Version: 4.3.0 New Comment: Exactly the same results w/ the same version of the gmp lib, and using PHP CLI compiled from CVS (Jan 3, 2003) on RH Linux 6.1 Previous Comments: ------------------------------------------------------------------------ [2003-01-08 19:15:37] jmcastagnetto@php.net More information. I found the following code: http://mail.gnu.org/archive/html/bug-gmp/2001-05/msg00061.html Which I then compiled w/ the gmp lib I have installed. Using that little C program that calls the gmp lib directly, the Diophantine equation mentioned in the bug submission gives the correct results: % ./a.out 1027 712 a = 1027 b = 712 d = 1 s = -165 t = 238 d =? 1 Which is the correct solution. And using a = 12 and b = 21: % ./a.out 12 21 a = 12 b = 21 d = 3 s = 2 t = -1 d =? 3 Bottomline: The GMP lib seems to be behaving OK, so maybe somewhere along the passing of the values from PHP to the lib the values are being corrupted? In view of this I had not sent a bug report to the GMP lib maintainers. ------------------------------------------------------------------------ [2003-01-08 18:56:44] jmcastagnetto@php.net 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 this bug report at http://bugs.php.net/?id=21534&edit=1