Toward faster Rationals

General Usage Performance
1

Consider (abs, inv, +, -, *, //) over values of type Rational{I}
where I<:Union{Int16…Int128, BigInt}. A substantive time sink is renormalizing the (numerator, denominator) pairs: div each by their gcd.

Use two sorts of Rationals, (1) those known to be reduced to lowest terms and (2) those not known to be reduced to lowest terms. And avoid the gcd stuff as long as possible while protecting the integrity of the calculation. Doing this obtains an arithmetically performant realization of bounded Rationals.

These occurrences prompt renormalization:

(a) an arithmetic op overflows and an operand is not known to be reduced    
    - normalize the operand[s] to lowest terms and retry the arithmetic op

(b) a Rational value that is not known to be reduced is obtained from a store or a stream   
    - normalize the value and pass that along, now known to be reduced
      
(c) a Rational value that is not known to be in lowest terms is offered (written to a store, displayed)   
    - normalize the value and utilize that, so all presentation is of canonical Rational forms

This is effective.

Implementing the type this way:

struct FastRational{IntForRational, TeleologicalState}
    numerator::IntForRational
    denominator::IntForRational
end

# where

const RationalInt =
     Union{Int8, Int16, Int32, Int64, Int128, BigInt}

const IsKnownToBeReduced    = Val{:IsKnownToBeReduced}
const IsNotKnownToBeReduced = Val{:IsNotKnownToBeReduced}
const TeleologicalState =
     Union{IsKnownToBeReduced, IsNotKnownToBeReduced}

works well with simple expressions

each NNx is from one expr on one machine
@btime (a_numer//a_denom) * (b_numer//b_denom))

  • relative to Rational{I}: Int32 (25x), Int64 (10x), BigInt (4x), Int128 (2x)

I am concerned that real world use may make normalization churn.

Algorithms that use many magnitude comparisons with values not known to be in reduced form could/would cause those values to be repeatedly re-reduced. The struct is immutable and the reduced forms, once derived, often would not persist. It seems that the mechanism above only allows values that are streamed out and later streamed in have their newly reduced state persist.

A much better way would be to have the representation allow for transitioning from the numerator and denominator values associated with a IsNotKnownToBeReduced state to reduced numerator and denominator values associated with a IsNotKnownToBeReduced state become (same referent, updated content) the reduced numerator and denominator values and morph its teleological state into IsKnownToBeReduced.


How may this be accomplished, keeping performance?

Simply changing the struct to a mutable struct (no other edits) halves the performance gains.

Taking advantage of the mutability may win back some time, but those gains stick only if the teleological state becomes a third field (so it can be altered without breaking type). Although adding to the struct size is not great for an otherwise juxtaposed primitive type pair.

Is there a clean way for that Bool field to govern dispatch as the parameterized version does … before runtime? It seems ad hock.

1 Like
2

The type definition could be kept simpler as

struct FastRational{T}
    num::T
    denom::T
end

with the only difference from Rational being that the canonical form of the rational is not enforced, so a*num and a*denom are the same rational, for positive integer a.

The following semantics could be accomplished with a minimal extension of the vocabulary:

  1. arithmetic on FastRationals results in FastRationals, which are not necessarily canonical,
  2. convert(Rational, x) provides the canonical form,
  3. FastRationals are contagious, eg +(::Rational, ::FastRational)::FastRational.

Whenever fast equality comparison is required, the user converts explicitly to Rational.

However, there is a trade-off here: for nontrivial calculations, the denominator can explode very quickly, so that BigInt is the only meaningful choice. But an occasional gcd may result in significantly smaller representation.

3

Most of the performance gain comes from being able to differentiate FastRationals that are reduced (and so their arith logic has a simpler path) from FastRationals that are not known to be reduced (i.e. those that have not been reduced explicitly). And handling the mixed case (2 operands, one reduced the other may not be reduced) is faster than the general case, so I do that.

I may be misunderstanding your intent, though.

4

My point was that these are already the Rational type. Unless promotion rules would be different, reduced FastRationals would be superfluous IMO, but I might be missing something.

5

Ahh. I tried something like that – got stuck here.

Using regular rationals is not helpful because – eventhough they are always reduced, the regular rational arith code keeps gcd-ing them, and that is most of the time difference. So I thought to make two types, say FastRational and FastRatio where FastRationalss were assured to be reduced and FastRatios never were assured to be reduced (though they might be). And thought about writing the code so they fully interoperate and I retain metamanagement of the postponements and manners of determining overflow.

So far so good … dispatch remains strongly helpful and both types inherit from a shared supertype to allow some code simplification.

Does this allow for a variable q that is created as a FastRatio and is computed on for while, and gets reduced for good reason – so it, as butterfly, becomes realized as a FastRational … does this allow for that variable, q to be reattached to the FastRational realization? And if so, can this occur rapidly enough (it would happen often)?

6

https://github.com/timholy/Ratios.jl

It’s not been extended beyond the simplest implementation, but might be a starting point.

7

Yes, that is as a gcd free variant of Rational{T} where T<:Signed. I have a gcd wary variant. And that is half 'n other half, perspectively.

Any familiarity with the proper way
(is there any proper way that does not totally go against principle)
to do this imagined manipulation?

struct Ratio{T}
   num::T
   den::T 
end

r0 = Ratio(4, 8)
r1 = Ratio(1, 2)

ptr_to_r0num = get_pointer(Ratio, r0, :num) # get_pointer(Ratio, r0, fieldidx = 1)
ptr_to_r0den = get_pointer(Ratio, r0, :den)  # get_pointer(Ratio, r0, fieldidx = 2)

unsafe_overwrite_into_struct(ptr_to_r0num, r1.num) # .., object_from_ptr(ptr_to_r1num)
unsafe_overwrite_into_struct(ptr_to_r0den, r1.den)

r0.num == r1.num && r0.den == r1.den
8

or like that using variables as pointer handles
or like that … would using SVectors of length 2 be appropriate? @andyferris

9

This may be one way (I have not made it yet, so performance is tbd).

Make FastRational a struct of two structs, one of type RationalIsReduced and the other of type RationalMayReduce where each has fields :num and :den. Parameterize FastRationals to include a param for either of two teleological Val{} types and use that to properly select dispatch before runtime.

10

SVector{2} models a 2D vector space; otherwise as a container it’s not much more useful than a 2-tuple, or a struct with two fields.