*Math Functions Bug #21534
https://bugs.php.net/bug.php?id=21534
[Closed] GMP lib gmp_gcdext() gives incorrect resultsWed, 08 Jan 2003 18:56:44 +0000Thu, 13 Mar 2003 10:20:37 +0000jmcastagnetto@... [2003-01-08 18:56:44]*Math Functions Bug
Reported by jmcastagnetto
Wed, 08 Jan 2003 18:56:44 +0000
PHP: 4.3.0, OS: Solaris 8
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. ]]>Wed, 08 Jan 2003 18:56:44 +0000https://bugs.php.net/bug.php?id=21534