inconsistent sign of gcd

[stevengj]

gcd(-7, 37) returns -1, but gcd(big(-7), big(37)) (via GMP) returns 1.

In the gcd(a,b) implementation in intfuncs.jl, there is an explicit rule that the gcd return value has the same sign as a. If there is a good reason for this rule(??), we should modify the BigInt call to implement the same rule (since GMP seems to always return a positive result).

[JeffBezanson]

It makes more sense to me for a gcd to be positive.

[stevengj]

For variety, Python's fractions.gcd function gives gcd(a,b) the same sign as b.

[johnmyleswhite]

I'd also prefer having gcd always return a positive value.

[stevengj]

If the gcd is the greatest common divisor, and the divisors are defined as positive integers, then it seems like the gcd should always be positive.

[stevengj]

Note that the same inconsistency occurs for lcm(a,b): GMP always returns a positive quantity, but our return value depends upon the signs of the arguments.

[StefanKarpinski]

If we make gcd and lcm always positive, then the Rational implementation will have to be modified. IIRC, having this return a value with the same sign as the first argument (which is the only one that's guaranteed to exist) makes certain algorithms much easier to write.

[StefanKarpinski]

I just checked that this means that construction of Rational{BigInt} values was broken:

julia> big(2)//big(-3)
2//-3

That should produce -2//3 instead.

[stevengj]

Since gcd is only used in two places in rational.jl, and the sign only matters in one place, it seems reasonable to just modify rational.jl to handle a positive gcd.

[StefanKarpinski]

Agreed. Just pointing out the issue.

[StefanKarpinski]

If anything, the fact that the difference between built-in integers and bigints was causing broken rational behavior demonstrates the fragility of relying on this rather subtle and non-obvious behavior. FWIW, the gcd and Rational type is some of the first Julia code we ever wrote – 70efab8.

[JeffBezanson]

Wow, I forgot about the conversion keyword. What were we thinking? :)

[stevengj]

By the way, the old behavior was also causing a bug in invmod, since that function was checking gcd(a,b) == 1 to decide whether the inverse exists. In my mind, checking gcd(a,b) == 1 should be a correct way to determine whether two numbers are coprime, and any other behavior is likely to be bug-inducing.

[StefanKarpinski]

Wow, I forgot about the conversion keyword. What were we thinking? :)

What we were thinking was "crap, how the hell are we going to deal with numeric conversion and promotion?" – because we hadn't yet figured out how to do all of it with dispatch. The conversion keyword was a terrible idea.