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
