Status: New
Owner: ----
New issue 895 by pierreAndre.laurent: gcd negative parameters
http://code.google.com/p/v8/issues/detail?id=895
spotted the following wrong code in the benchmarks
function sc_euclid_gcd(a, b) {
var temp;
if (a === 0) return b;
if (b === 0) return a;
if (a < 0) {a = -a;};
if (b < 0) {b = -b;};
if (b > a) {temp = a; a = b; b = temp;};
while (true) {
a %= b;
if(a === 0) {return b;};
b %= a;
if(b === 0) {return a;};
};
return b;
}
BUG: The code does NOT respect the following invariants
gcd (a, b) == gcd(a + b, b)
gcd (a, b) == gcd(a, a + b)
which means the code should be closer to this functional description
while (a < 0) a += abs(b)
while (b < 0) b += abs(a)
however, this is nearly an infinite loop, the following converges faster.
if (a < 0)
{
t = abs(b);
while (a < 0)
{
a += t;
t <<= 1;
}
if (a == 0) return abs(b);
}
and symmetrically for b
if (b < 0)
{
t = abs(a);
while (b < 0)
{
b += t;
t <<= 1;
}
if (b == 0) return abs(a);
}
There are plenty other methods to get the same result.
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
