php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #21534 GMP lib gmp_gcdext() gives incorrect results
Submitted: 2003-01-08 18:56 UTC Modified: 2003-03-13 10:20 UTC
Votes:2
Avg. Score:5.0 ± 0.0
Reproduced:2 of 2 (100.0%)
Same Version:0 (0.0%)
Same OS:0 (0.0%)
From: jmcastagnetto@php.net Assigned:
Status: Closed Package: *Math Functions
PHP Version: 4.3.0 OS: Solaris 8
Private report: No CVE-ID:
 [2003-01-08 18:56 UTC] 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.

Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2003-01-08 19:15 UTC] 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 23:50 UTC] jmcastagnetto@php.net
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
 [2003-03-13 10:20 UTC] pollita@php.net
This bug has been fixed in CVS.

In case this was a PHP problem, snapshots of the sources are packaged
every three hours; this change will be in the next snapshot. You can
grab the snapshot at http://snaps.php.net/.
 
In case this was a documentation problem, the fix will show up soon at
http://www.php.net/manual/.

In case this was a PHP.net website problem, the change will show
up on the PHP.net site and on the mirror sites in short time.
 
Thank you for the report, and for helping us make PHP better.

PHP layer was passing arg 1 twice.

So in your example with a=1027 and b=712 What was reaching the gmp library was a=1027 and b=1027

so the solution:

1027*1 + 1027*0 = 1027 was true (in so far as the library was concerned)
 
PHP Copyright © 2001-2014 The PHP Group
All rights reserved.
Last updated: Thu Apr 17 18:02:13 2014 UTC