gcd, lcm, gcdx for Rational

[KlausC]

Tackles issue #27039.

[KlausC]

@ararslan , @StefanKarpinski the missing documentation has been added.
Isn't his is one of those tiny changes, which considerably extend the domain of the language.

[KlausC]

bump

[StefanKarpinski]

Thanks, @KlausC! Will be in 1.4.

[sostock]

I would have preferred a slightly different implementation. For example, instead of

gcd(a::Union{Integer,Rational}, b::Union{Integer,Rational}) = gcd(promote(a,b)...)

I would have preferred

gcd(a::Real, b::Real) = gcd(promote(a,b)...)
gcd(a::T, b::T) where T<:Real = throw(MethodError(gcd, (a, b)))

This would make it easier to extend gcd to other numeric types. If I want to add gcd support to HalfIntegers.jl, I now have to write

Base.gcd(x::HalfInteger) = x
Base.lcm(x::HalfInteger) = x

Base.gcd(a::T, b::T) where T<:HalfInteger = ACTUAL CODE
Base.lcm(a::T, b::T) where T<:HalfInteger = ACTUAL CODE
Base.gcdx(x::T, y::T) where T<:HalfInteger = ACTUAL CODE

const IntOrRatOrHalf = Union{Integer, Rational, HalfInteger}
Base.lcm(a::IntOrRatOrHalf, b::IntOrRatOrHalf) = lcm(promote(a,b)...)
Base.gcd(a::IntOrRatOrHalf, b::IntOrRatOrHalf) = gcd(promote(a,b)...)
Base.lcm(a::IntOrRatOrHalf, b::IntOrRatOrHalf...) = lcm(a, lcm(b...))
Base.gcd(a::IntOrRatOrHalf, b::IntOrRatOrHalf...) = gcd(a, gcd(b...))
Base.gcdx(a::IntOrRatOrHalf, b::IntOrRatOrHalf) = gcdx(promote(a,b)...)

Base.lcm(abc::AbstractArray{<:IntOrRatOrHalf}) = reduce(lcm, abc; init=one(eltype(abc)))

function Base.gcd(abc::AbstractArray{<:IntOrRatOrHalf})
    a = zero(eltype(abc))
    for b in abc
        a = gcd(a,b)
        if a == 1
            return a
        end
    end
    return a
end

where everything below and including the const IntOrRatOrHalf line is boilerplate code that mirrors the implementation from Base, only adding another type to the Union. This could be avoided if the Base implementation were changed as I suggested above.

In my opinion, this is important for the interoperability between packages. If there are two packages which define types numeric types A and B, getting gcd(::A, ::B) to work currently requires to write another version of the boilerplate code above with the types A and B added to the Union. With the implementation that I propose, they would only have to implement promotion rules.

What do you think about this? Should I open an issue or submit a PR?

[StefanKarpinski]

I'm a bit unclear on what the issue there is: shouldn't integers and half-integers promote to half-integers? That seems like it should "just work". Similarly, half-integers and rationals should promote to rationals, which should also "just work". Is the issue that you want to intercept mixed type?

[sostock]

No, the issue is that I have to implement

const IntOrRatOrHalf = Union{Integer, Rational, HalfInteger}
Base.gcd(a::IntOrRatOrHalf, b::IntOrRatOrHalf) = gcd(promote(a,b)...)

and a bunch of other methods, since there is no gcd(::Real, ::Real) implementation in Base that does the promotion. There is only gcd(::Union{Integer, Rational}, ::Union{Integer, Rational}), and I need a method for Union{Integer, Rational, HalfInteger} arguments. Using Real instead of Union{Integer,Rational} would solve this.

Promoting HalfIntegers, Rationals, and Integers does work, but gcd doesn’t use the promotion, because HalfInteger is not <:Union{Integer,Rational}. I do not want to intercept mixed types, I want to rely on promotion. But there is no

gcd(a::Real, b::Real) = gcd(promote(a,b)...)

There is only

gcd(a::Union{Integer,Rational}, b::Union{Integer,Rational}) = gcd(promote(a,b)...)

[StefanKarpinski]

It seems like HalfInteger should perhaps be a subtype of Rational, no?

[StefanKarpinski]

Except that we'd need to have AbstractRational, which we don't have. So I see the problem.

[sostock]

Are there plans to add an AbstractRational type? Otherwise, I don’t see how I could do that.

Edit: you were a couple of seconds quicker

[sostock]

By the way, there are at least two other operations that also define their fallback methods for Real, not for some Union, and then throw a MethodError when there is no method for the promoted arguments. So my proposed implementation is not unprecedented:

julia/base/div.jl

Lines 232 to 233 in 074974a

	fld(x::T, y::T) where {T<:Real} = throw(MethodError(div, (x, y, RoundDown)))
	cld(x::T, y::T) where {T<:Real} = throw(MethodError(div, (x, y, RoundUp)))

[sostock]

Should I just make a PR?

[StefanKarpinski]

Sure, go for it.