[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.