follows PR for improving `rationals.jl`, renames `Rational` to `Fraction`, renames `//` to `⨸`

Fractions.jl

# 2020-04-24 11:03 UTC, module follows PR for improving `rationals.jl`
# This file is a part of Julia. License is MIT: https://julialang.org/license

module Fractions

export Fraction, ⨸

import Base: show, read, write, fma,
             BitSigned, Bool, AbstractFloat, big, BigInt, float,
             ==, !=, >, >=, <, <=, isequal, isless,
             zero, one, iszero, isone, isinteger,
             checked_add, checked_sub, checked_mul,
             +, -, *, inv, /, //, rationalize,
             div, rem, mod, fld, cld, divrem, gcd, lcm, gcdx, divgcd,             
             promote_rule, convert, promote_type,
             numerator, denominator, typemin, typemax,
             signbit, copysign, flipsign, widen, abs, abs2
			 
"""
    Fraction{T<:Integer} <: Real

Fraction number type, with numerator and denominator of type `T`.
Fractions are checked for overflow.
"""
struct Fraction{T<:Integer} <: Real
    num::T
    den::T

    function Fraction{T}(num::T1, den::T1; checked::Bool) where {T<:Integer, T1<:Integer}
        if checked
            iszero(den) && iszero(num) && __throw_fraction_argerror_zero(T)
            num, den = divgcd(num, den)
            num, den = checking_den(T(num), T(den))
        end
        return new{T}(num, den)
    end
end

Fraction{T}(num::Integer, den::Integer; checked::Bool) where T<:Integer =
    Fraction{T}(promote(num, den)...; checked=checked)
	
@noinline __throw_fraction_argerror_zero(T) = throw(ArgumentError("invalid fraction: zero($T)⨸zero($T)"))
@noinline __throw_fraction_argerror_typemin(T) = throw(ArgumentError("invalid fraction: denominator can't be typemin($T)"))

function checking_den(num::T, den::T) where T<:Integer
    if signbit(den)
        den = -den
        signbit(den) && __throw_fraction_argerror_typemin(T)
        num = -num
    end
    return num, den
end

function checked_den(num::T, den::T) where T<:Integer
    Fraction{T}(checking_den(num, den)...; checked=false)
end
checked_den(num::Integer, den::Integer) = checked_den(promote(num, den)...)

function Fraction{T}(num::Integer, den::Integer) where T<:Integer
    Fraction{T}(num, den; checked=true)
end

function Fraction(n::T, d::T; checked=true) where T<:Integer
    Fraction{T}(n, d; checked=checked)
end

"""
    Fraction(num::Integer, den::Integer; checked::Bool=true)
    Fraction{T<:Integer}(num::Integer, den::Integer; checked::Bool=true)

Create a `Fraction` with numerator `num` and denominator `den`.

A `Fraction` is well-formed if its numerator and denominator are coprime and if the
denominator is non-negative. By default, the constructor checks its arguments so that
the created `Fraction` is well-formed. Well-formedness is kept across operations on
`Fraction`s.

Unset the optional argument `checked` to bypass all checks.

!!! warning
    Using an ill-formed `Fraction` result in undefined behavior. Only bypass checks if
    `num` and `den` are known to satisfy them.
"""
function Fraction(n::Integer, d::Integer; checked=true)
    Fraction(promote(n, d)...; checked=checked)
end
Fraction(n::Integer) = Fraction(n, one(n); checked=false)

Fraction(q::Base.Rational{T}) where {T<:Integer} = Fraction{T}(numerator(q), denominator(q); checked=false)
Fraction{T}(q::Base.Rational) where {T<:Integer} = Fraction{T}(T(numerator(q)), T(denominator(q)); checked=false)
Base.Rational(q::Fraction{T}) where {T<:Integer} = Base.Rational{T}(numerator(q), denominator(q))
Base.Rational{T}(q::Fraction) where {T<:Integer} = Base.Rational{T}(T(numerator(q)), T(denominator(q)))

function divgcd(x::Integer,y::Integer)
    g = gcd(x,y)
    div(x,g), div(y,g)
end

"""
    ⨸(num, den)

Divide two integers or fraction numbers, giving a [`Fraction`](@ref) result.

# Examples
```jldoctest
julia> 3 ⨸ 5
3⨸5

julia> (3 ⨸ 5) ⨸ (2 ⨸ 1)
3⨸10
```
"""
⨸(n::Integer,  d::Integer) = Fraction(n,d)

function ⨸(x::Fraction, y::Integer)
    xn, yn = divgcd(x.num,y)
    checked_den(xn, checked_mul(x.den, yn))
end
function ⨸(x::Integer,  y::Fraction)
    xn, yn = divgcd(x,y.num)
    checked_den(checked_mul(xn, y.den), yn)
end
function ⨸(x::Fraction, y::Fraction)
    xn,yn = divgcd(x.num,y.num)
    xd,yd = divgcd(x.den,y.den)
    checked_den(checked_mul(xn, yd), checked_mul(xd, yn))
end

⨸(x::Complex, y::Real) = complex(real(x)⨸y, imag(x)⨸y)
⨸(x::Number, y::Complex) = x*conj(y)⨸abs2(y)


⨸(X::AbstractArray, y::Number) = X .⨸ y

function show(io::IO, x::Fraction)
    show(io, numerator(x))
    print(io, "⨸")
    show(io, denominator(x))
end

function read(s::IO, ::Type{Fraction{T}}) where T<:Integer
    r = read(s,T)
    i = read(s,T)
    r⨸i
end
function write(s::IO, z::Fraction)
    write(s,numerator(z),denominator(z))
end

function Fraction{T}(x::Fraction) where T<:Integer
    Fraction{T}(convert(T, x.num), convert(T,x.den); checked=false)
end
function Fraction{T}(x::Integer) where T<:Integer
    Fraction{T}(convert(T, x), one(T); checked=false)
end

Fraction(x::Fraction) = x

Bool(x::Fraction) = x==0 ? false : x==1 ? true :
    throw(InexactError(:Bool, Bool, x)) # to resolve ambiguity
(::Type{T})(x::Fraction) where {T<:Integer} = (isinteger(x) ? convert(T, x.num) :
    throw(InexactError(nameof(T), T, x)))

AbstractFloat(x::Fraction) = float(x.num)/float(x.den)
function (::Type{T})(x::Fraction{S}) where T<:AbstractFloat where S
    P = promote_type(T,S)
    convert(T, convert(P,x.num)/convert(P,x.den))
end

function Fraction{T}(x::AbstractFloat) where T<:Integer
    r = rationalize(T, x, tol=0)
    x == convert(typeof(x), r) || throw(InexactError(:Fraction, Fraction{T}, x))
    r
end
Fraction(x::Float64) = Fraction{Int64}(x)
Fraction(x::Float32) = Fraction{Int}(x)

big(q::Fraction) = Fraction(big(numerator(q)), big(denominator(q)); checked=false)

big(z::Complex{<:Fraction{<:Integer}}) = Complex{Fraction{BigInt}}(z)

promote_rule(::Type{Fraction{T}}, ::Type{S}) where {T<:Integer,S<:Integer} = Fraction{promote_type(T,S)}
promote_rule(::Type{Fraction{T}}, ::Type{Fraction{S}}) where {T<:Integer,S<:Integer} = Fraction{promote_type(T,S)}
promote_rule(::Type{Fraction{T}}, ::Type{S}) where {T<:Integer,S<:AbstractFloat} = promote_type(T,S)

widen(::Type{Fraction{T}}) where {T} = Fraction{widen(T)}

"""
    rationalize([T<:Integer=Int,] x; tol::Real=eps(x))

Approximate floating point number `x` as a [`Fraction`](@ref) number with components
of the given integer type. The result will differ from `x` by no more than `tol`.

# Examples
```jldoctest
julia> rationalize(5.6)
28⨸5

julia> a = rationalize(BigInt, 10.3)
103⨸10

julia> typeof(numerator(a))
BigInt
```
"""
function rationalize(::Type{T}, x::AbstractFloat, tol::Real) where T<:Integer
    if tol < 0
        throw(ArgumentError("negative tolerance $tol"))
    end
    if T<:Unsigned && x < 0
        throw(OverflowError("cannot negate unsigned number"))
    end
    isnan(x) && return T(x)⨸one(T)
    isinf(x) && return Fraction(x < 0 ? -one(T) : one(T), zero(T); checked=false)

    p,  q  = (x < 0 ? -one(T) : one(T)), zero(T)
    pp, qq = zero(T), one(T)

    x = abs(x)
    a = trunc(x)
    r = x-a
    y = one(x)

    tolx = oftype(x, tol)
    nt, t, tt = tolx, zero(tolx), tolx
    ia = np = nq = zero(T)

    # compute the successive convergents of the continued fraction
    #  np ⨸ nq = (p*a + pp) ⨸ (q*a + qq)
    while r > nt
        try
            ia = convert(T,a)

            np = checked_add(checked_mul(ia,p),pp)
            nq = checked_add(checked_mul(ia,q),qq)
            p, pp = np, p
            q, qq = nq, q
        catch e
            isa(e,InexactError) || isa(e,OverflowError) || rethrow()
            return p ⨸ q
        end

        # naive approach of using
        #   x = 1/r; a = trunc(x); r = x - a
        # is inexact, so we store x as x/y
        x, y = y, r
        a, r = divrem(x,y)

        # maintain
        # x0 = (p + (-1)^i * r) / q
        t, tt = nt, t
        nt = a*t+tt
    end

    # find optimal semiconvergent
    # smallest a such that x-a*y < a*t+tt
    a = cld(x-tt,y+t)
    try
        ia = convert(T,a)
        np = checked_add(checked_mul(ia,p),pp)
        nq = checked_add(checked_mul(ia,q),qq)
        return np ⨸ nq
    catch e
        isa(e,InexactError) || isa(e,OverflowError) || rethrow()
        return p ⨸ q
    end
end
rationalize(::Type{T}, x::AbstractFloat; tol::Real = eps(x)) where {T<:Integer} = rationalize(T, x, tol)::Fraction{T}
rationalize(x::AbstractFloat; kvs...) = rationalize(Int, x; kvs...)

"""
    numerator(x)

Numerator of the fraction representation of `x`.

# Examples
```jldoctest
julia> numerator(2⨸3)
2

julia> numerator(4)
4
```
"""
numerator(x::Integer) = x
numerator(x::Fraction) = x.num

"""
    denominator(x)

Denominator of the fraction representation of `x`.

# Examples
```jldoctest
julia> denominator(2⨸3)
3

julia> denominator(4)
1
```
"""
denominator(x::Integer) = one(x)
denominator(x::Fraction) = x.den

sign(x::Fraction) = oftype(x, sign(x.num))
signbit(x::Fraction) = signbit(x.num)
copysign(x::Fraction, y::Real) = Fraction(copysign(x.num, y), x.den; checked=false)
copysign(x::Fraction, y::Fraction) = Fraction(copysign(x.num, y.num), x.den; checked=false)

abs(x::Fraction) = Fraction(abs(x.num), x.den)

typemin(::Type{Fraction{T}}) where {T<:Signed} = Fraction(-one(T), zero(T); checked=false)
typemin(::Type{Fraction{T}}) where {T<:Integer} = Fraction(zero(T), one(T); checked=false)
typemax(::Type{Fraction{T}}) where {T<:Integer} = Fraction(one(T), zero(T); checked=false)

isinteger(x::Fraction) = x.den == 1

+(x::Fraction) = Fraction(+x.num, x.den; checked=false)
-(x::Fraction) = Fraction(-x.num, x.den; checked=false)

function -(x::Fraction{T}) where T<:BitSigned
    x.num == typemin(T) && throw(OverflowError("fraction numerator is typemin(T)"))
    Fraction(-x.num, x.den; checked=false)
end
function -(x::Fraction{T}) where T<:Unsigned
    x.num != zero(T) && throw(OverflowError("cannot negate unsigned number"))
    x
end

for (op,chop) in ((:+,:checked_add), (:-,:checked_sub), (:rem,:rem), (:mod,:mod))
    @eval begin
        function ($op)(x::Fraction, y::Fraction)
            xd, yd = divgcd(x.den, y.den)
            Fraction(($chop)(checked_mul(x.num,yd), checked_mul(y.num,xd)), checked_mul(x.den,yd))
        end

        function ($op)(x::Fraction, y::Integer)
            Fraction(($chop)(x.num, checked_mul(x.den, y)), x.den; checked=false)
        end
    end
end
for (op,chop) in ((:+,:checked_add), (:-,:checked_sub))
    @eval begin
        function ($op)(y::Integer, x::Fraction)
            Fraction(($chop)(checked_mul(x.den, y), x.num), x.den; checked=false)
        end
    end
end
for (op,chop) in ((:rem,:rem), (:mod,:mod))
    @eval begin
        function ($op)(y::Integer, x::Fraction)
            Fraction(($chop)(checked_mul(x.den, y), x.num), x.den)
        end
    end
end

function *(x::Fraction, y::Fraction)
    xn, yd = divgcd(x.num, y.den)
    xd, yn = divgcd(x.den, y.num)
    Fraction(checked_mul(xn, yn), checked_mul(xd, yd); checked=false)
end
function *(x::Fraction, y::Integer)
    xd, yn = divgcd(x.den, y)
    Fraction(checked_mul(x.num, yn), xd; checked=false)
end
function *(y::Integer, x::Fraction)
    yn, xd = divgcd(y, x.den)
    Fraction(checked_mul(yn, x.num), xd; checked=false)
end
/(x::Fraction, y::Union{Fraction, Integer}) = x⨸y
/(x::Integer, y::Fraction) = x⨸y
/(x::Fraction, y::Complex{<:Union{Integer,Fraction}}) = x⨸y
function inv(x::Fraction{T}) where T
    checked_den(x.den, x.num)
end

fma(x::Fraction, y::Fraction, z::Fraction) = x*y+z

==(x::Fraction, y::Fraction) = (x.den == y.den) & (x.num == y.num)
<( x::Fraction, y::Fraction) = x.den == y.den ? x.num < y.num :
                               widemul(x.num,y.den) < widemul(x.den,y.num)
<=(x::Fraction, y::Fraction) = x.den == y.den ? x.num <= y.num :
                               widemul(x.num,y.den) <= widemul(x.den,y.num)


==(x::Fraction, y::Integer ) = (x.den == 1) & (x.num == y)
==(x::Integer , y::Fraction) = y == x
<( x::Fraction, y::Integer ) = x.num < widemul(x.den,y)
<( x::Integer , y::Fraction) = widemul(x,y.den) < y.num
<=(x::Fraction, y::Integer ) = x.num <= widemul(x.den,y)
<=(x::Integer , y::Fraction) = widemul(x,y.den) <= y.num

function ==(x::AbstractFloat, q::Fraction)
    if isfinite(x)
        (count_ones(q.den) == 1) & (x*q.den == q.num)
    else
        x == q.num/q.den
    end
end

==(q::Fraction, x::AbstractFloat) = x == q

for rel in (:<,:<=,:cmp)
    for (Tx,Ty) in ((Fraction,AbstractFloat), (AbstractFloat,Fraction))
        @eval function ($rel)(x::$Tx, y::$Ty)
            if isnan(x)
                $(rel === :cmp ? :(return isnan(y) ? 0 : 1) :
                                :(return false))
            end
            if isnan(y)
                $(rel === :cmp ? :(return -1) :
                                :(return false))
            end

            xn, xp, xd = decompose(x)
            yn, yp, yd = decompose(y)

            if xd < 0
                xn = -xn
                xd = -xd
            end
            if yd < 0
                yn = -yn
                yd = -yd
            end

            xc, yc = widemul(xn,yd), widemul(yn,xd)
            xs, ys = sign(xc), sign(yc)

            if xs != ys
                return ($rel)(xs,ys)
            elseif xs == 0
                # both are zero or ±Inf
                return ($rel)(xn,yn)
            end

            xb, yb = ndigits0z(xc,2) + xp, ndigits0z(yc,2) + yp

            if xb == yb
                xc, yc = promote(xc,yc)
                if xp > yp
                    xc = (xc<<(xp-yp))
                else
                    yc = (yc<<(yp-xp))
                end
                return ($rel)(xc,yc)
            else
                return xc > 0 ? ($rel)(xb,yb) : ($rel)(yb,xb)
            end
        end
    end
end

# needed to avoid ambiguity between ==(x::Real, z::Complex) and ==(x::Fraction, y::Number)
==(z::Complex , x::Fraction) = isreal(z) & (real(z) == x)
==(x::Fraction, z::Complex ) = isreal(z) & (real(z) == x)

function div(x::Fraction, y::Integer, r::RoundingMode)
    xn,yn = divgcd(x.num,y)
    div(xn, checked_mul(x.den,yn), r)
end
function div(x::Integer, y::Fraction, r::RoundingMode)
    xn,yn = divgcd(x,y.num)
    div(checked_mul(xn,y.den), yn, r)
end
function div(x::Fraction, y::Fraction, r::RoundingMode)
    xn,yn = divgcd(x.num,y.num)
    xd,yd = divgcd(x.den,y.den)
    div(checked_mul(xn,yd), checked_mul(xd,yn), r)
end

# For compatibility - to be removed in 2.0 when the generic fallbacks
# are removed from div.jl
div(x::T, y::T, r::RoundingMode) where {T<:Fraction} =
    invoke(div, Tuple{Fraction, Fraction, RoundingMode}, x, y, r)
for (S, T) in ((Fraction, Integer), (Integer, Fraction), (Fraction, Fraction))
    @eval begin
        div(x::$S, y::$T) = div(x, y, RoundToZero)
        fld(x::$S, y::$T) = div(x, y, RoundDown)
        cld(x::$S, y::$T) = div(x, y, RoundUp)
    end
end

trunc(::Type{T}, x::Fraction) where {T} = convert(T,div(x.num,x.den))
floor(::Type{T}, x::Fraction) where {T} = convert(T,fld(x.num,x.den))
ceil(::Type{T}, x::Fraction) where {T} = convert(T,cld(x.num,x.den))
round(::Type{T}, x::Fraction, r::RoundingMode=RoundNearest) where {T} = _round_fraction(T, x, r)
round(x::Fraction, r::RoundingMode) = round(Fraction, x, r)

function _round_fraction(::Type{T}, x::Fraction{Tr}, ::RoundingMode{:Nearest}) where {T,Tr}
    if denominator(x) == zero(Tr) && T <: Integer
        throw(DivideError())
    elseif denominator(x) == zero(Tr)
        return convert(T, copysign(Fraction(one(Tr), zero(Tr); checked=false), numerator(x)))
    end
    q,r = divrem(numerator(x), denominator(x))
    s = q
    if abs(r) >= abs((denominator(x)-copysign(Tr(4), numerator(x))+one(Tr)+iseven(q))>>1 + copysign(Tr(2), numerator(x)))
        s += copysign(one(Tr),numerator(x))
    end
    convert(T, s)
end

function _round_fraction(::Type{T}, x::Fraction{Tr}, ::RoundingMode{:NearestTiesAway}) where {T,Tr}
    if denominator(x) == zero(Tr) && T <: Integer
        throw(DivideError())
    elseif denominator(x) == zero(Tr)
        return convert(T, copysign(Fraction(one(Tr), zero(Tr); checked=false), numerator(x)))
    end
    q,r = divrem(numerator(x), denominator(x))
    s = q
    if abs(r) >= abs((denominator(x)-copysign(Tr(4), numerator(x))+one(Tr))>>1 + copysign(Tr(2), numerator(x)))
        s += copysign(one(Tr),numerator(x))
    end
    convert(T, s)
end

function _round_fraction(::Type{T}, x::Fraction{Tr}, ::RoundingMode{:NearestTiesUp}) where {T,Tr}
    if denominator(x) == zero(Tr) && T <: Integer
        throw(DivideError())
    elseif denominator(x) == zero(Tr)
        return convert(T, copysign(Fraction(one(Tr), zero(Tr); checked=false), numerator(x)))
    end
    q,r = divrem(numerator(x), denominator(x))
    s = q
    if abs(r) >= abs((denominator(x)-copysign(Tr(4), numerator(x))+one(Tr)+(numerator(x)<0))>>1 + copysign(Tr(2), numerator(x)))
        s += copysign(one(Tr),numerator(x))
    end
    convert(T, s)
end

function round(::Type{T}, x::Fraction{Bool}, ::RoundingMode=RoundNearest) where T
    if denominator(x) == false && (T <: Union{Integer, Bool})
        throw(DivideError())
    end
    convert(T, x)
end

trunc(x::Fraction{T}) where {T} = Fraction(trunc(T,x))
floor(x::Fraction{T}) where {T} = Fraction(floor(T,x))
ceil(x::Fraction{T}) where {T} = Fraction(ceil(T,x))
round(x::Fraction{T}) where {T} = Fraction(round(T,x))

function ^(x::Fraction, n::Integer)
    n >= 0 ? power_by_squaring(x,n) : power_by_squaring(inv(x),-n)
end

^(x::Number, y::Fraction) = x^(y.num/y.den)
^(x::T, y::Fraction) where {T<:AbstractFloat} = x^convert(T,y)
^(z::Complex{T}, p::Fraction) where {T<:Real} = z^convert(typeof(one(T)^p), p)

^(z::Complex{<:Fraction}, n::Bool) = n ? z : one(z) # to resolve ambiguity
function ^(z::Complex{<:Fraction}, n::Integer)
    n >= 0 ? power_by_squaring(z,n) : power_by_squaring(inv(z),-n)
end

iszero(x::Fraction) = iszero(numerator(x))
isone(x::Fraction) = isone(numerator(x)) & isone(denominator(x))

function lerpi(j::Integer, d::Integer, a::Fraction, b::Fraction)
    ((d-j)*a)/d + (j*b)/d
end

float(::Type{Fraction{T}}) where {T<:Integer} = float(T)

gcd(x::Fraction, y::Fraction) = Fraction(gcd(x.num, y.num), lcm(x.den, y.den); checked=false)
lcm(x::Fraction, y::Fraction) = Fraction(lcm(x.num, y.num), gcd(x.den, y.den); checked=false)
function gcdx(x::Fraction, y::Fraction)
    c = gcd(x, y)
    if iszero(c.num)
        a, b = one(c.num), c.num
    elseif iszero(c.den)
        a = ifelse(iszero(x.den), one(c.den), c.den)
        b = ifelse(iszero(y.den), one(c.den), c.den)
    else
        idiv(x, c) = div(x.num, c.num) * div(c.den, x.den)
        _, a, b = gcdx(idiv(x, c), idiv(y, c))
    end
    c, a, b
end

end  #  Fractions