summary of rational.jl improvements and questions for #triage

rational_pr_summary_for_triage.md

In Breif

Over five years, members of the community have been discussing Julia's Rational Number implementation and experimenting with modifications intended to increase the performance of Rational arithmetic while protecting correctness and catching arithmetic exceptions (overflow, underflow, division by zero).

We have an approach that speeds up correct multiplication (division). The prod of 12 rationals is faster than v1.4.1 by at least 1.5x using Rational{Int64}, 1.25x using Rational{BigInt}. In this implementation, rational addition, subtraction do not speed up.

There are several ways to approach coding the core constructor. The specifics are discussed in this PR. We ask #triage to choose which it deem the most appropriate.

The Construction Approaches

details, discussion and source code are here

using no keywords

const CheckTheSign  = true
const OmitSignCheck = false

struct Rational{T<:Integer} <: Real
    num::T
    den::T

    function Rational{T}(num::T, den::T, checksign::Bool) where {T<:Integer}
        if T<:Signed && checksign && signbit(den)
            den = -den
            signbit(den) && __throw_rational_argerror_typemin(T)
            num = -num
        end
        return new{T}(num, den)
    end
end

function Rational{T}(num::T, den::T) where {T<:Integer}
    num == den == zero(T) && __throw_rational_argerror_zero(T)
    num2, den2 = divgcd(num, den)
    return Rational{T}(num2, den2, CheckTheSign)
end

Rational(num::T, den::T) where {T<:Integer} = Rational{T}(num, den)

using one keyword

const CheckTheSign  = true
const OmitSignCheck = false

struct Rational{T<:Integer} <: Real
    num::T
    den::T

    function Rational{T}(num::T, den::T; checksign::Bool) where {T<:Integer}
        if T<:Signed && checksign && signbit(den)
            den = -den
            signbit(den) && __throw_rational_argerror_typemin(T)
            num = -num
        end
        return new{T}(num, den)
    end
end

function Rational{T}(num::T, den::T) where {T<:Integer}
    num == den == zero(T) && __throw_rational_argerror_zero(T)
    num2, den2 = divgcd(num, den)
    return Rational{T}(num2, den2, checksign=CheckTheSign)
end

Rational(num::T, den::T) where {T<:Integer} = Rational{T}(num, den)

using two keywords (default true)

"""
    Rational(num::Integer, den::Integer; safe::Bool=true, checksign::Bool=safe)
    Rational{T<:Integer}(num::Integer, den::Integer; safe::Bool=true, checksign::Bool=safe)

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

A `Rational` is well-formed when (a) its denominator is non-negative and
(b) numerator and denominator are coprime. With the keyword defaults,
constructed `Rationals` are well-formed. Operating on well-formed Rationals
will generate well-formed results.

Unset the optional argument `checksign` to bypass the check on the sign of `den`.
Unset the optional argument `safe` to bypass the coprimality check. 
By default, unsetting `safe` also unsets `checksign`.

!!! warning
    Using an ill-formed `Rational` may result in undefined behavior.
    Only bypass checks if `num` and `den` are already known to satisfy the checks.
"""
struct Rational{T<:Integer} <: Real
    num::T
    den::T

    function Rational{T}(num::Integer, den::Integer; safe::Bool=true, checksign::Bool=safe) where T<:Integer
        if safe
            num == den == zero(T) && __throw_rational_argerror_zero(T)
            num, den = divgcd(num, den)
        end
        if T<:Signed && checksign && signbit(den)
            den = -den
            signbit(den) && __throw_rational_argerror_typemin(T)
            num = -num
        end
        return new{T}(num, den)
    end
end

function Rational(n::T, d::T; safe=true, checksign=safe) where T<:Integer
    Rational{T}(n, d; safe, checksign)
end

using an internal, functional struct with one keyword (default false)

struct unsafe_rational{T<:Integer} <: Function end

struct Rational{T<:Integer} <: Real
    num::T
    den::T

    function (::Type{unsafe_rational{T}})(num::Integer, den::Integer; checksign::Bool=false) where T<:Integer
        if T<:Signed && checksign && signbit(den)
            den = -den
            signbit(den) && __throw_rational_argerror_typemin(T)
            num = -num
        end
        return new{T}(num, den)
    end
end

function Rational{T}(num::Integer, den::Integer) where T<:Integer
    num == den == zero(T) && __throw_rational_argerror_zero(T)
    num2, den2 = divgcd(num, den)
    return unsafe_rational{T}(num2, den2; checksign=true)
end

Discussions and Packages

• On 2020-Apr-15, @Liozou opened this PR Faster Rationals by avoiding unnecessary divgcd.
• On 2019-Jul-15 @JeffreySarnoff (with @KlausC) released FastRationals.jl.
• On 2017-May-22, @tim.holy released Ratios.jl.
• On 2015-Jun-01, @tim.holy opened this issue Faster Rational-like type.

Contributors (by date)

• Tim Holy (@tim.holy)
• Simon Byrne (@simonbyrne)
• Stefan Karpinski (@StefanKarpinski)
• Ian Dunning (@IanNZ)
• Jim Garrison (@garrison)
• Jeff Bezanson (@JeffBezanson)
• Andy Hayden (@hayd)
• Oscar Smith (@oscardssmith)
• Jeffrey Sarnoff (@JeffreySarnoff)
• Klaus Crusius (@KlausC)
• Gilles Peiffer (@Peiffap)
• Xing Shi Cai (@newptcai)
• Liozou (@Liozou)
• Kristoffer Carlsson (@KristofferC)
• Simon Schaub (@simeonschaub)
• Mustafa M. (@musm)