# Toward faster Rationals
**URL:** https://discourse.julialang.org/t/toward-faster-rationals/7933
**Category:** Performance
**Created:** [December 23, 2017, 12:13am UTC](https://discourse.julialang.org/t/toward-faster-rationals/7933 "2017-12-23T00:13:26Z")
**Posts on this page:** 10
**Page:** 1
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [December 23, 2017, 12:13am UTC](https://discourse.julialang.org/t/toward-faster-rationals/7933/1 "2017-12-23T00:13:26Z")
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:
```julia
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`.
```julia
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.
---
### Author:  [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)
#### Post date: [December 23, 2017, 6:55am UTC](https://discourse.julialang.org/t/toward-faster-rationals/7933/2 "2017-12-23T06:55:20Z")
The type definition could be kept simpler as
```julia
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 `FastRational`s results in `FastRational`s, which are not necessarily canonical,
2. `convert(Rational, x)` provides the canonical form,
3. `FastRational`s 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.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [December 23, 2017, 7:00am UTC](https://discourse.julialang.org/t/toward-faster-rationals/7933/3 "2017-12-23T07:00:10Z")
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.
---
### Author:  [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)
#### Post date: [December 23, 2017, 7:15am UTC](https://discourse.julialang.org/t/toward-faster-rationals/7933/4 "2017-12-23T07:15:35Z")
> [@JeffreySarnoff](#):
>
> FastRationals that are reduced
My point was that these are already the `Rational` type. Unless promotion rules would be different, reduced `FastRational`s would be superfluous IMO, but I might be missing something.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [December 23, 2017, 7:31am UTC](https://discourse.julialang.org/t/toward-faster-rationals/7933/5 "2017-12-23T07:31:20Z")
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 `FastRationals`s were assured to be reduced and `FastRatio`s 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)?
---
### Author:  [@tim.holy](https://discourse.julialang.org/u/tim.holy)
#### Post date: [December 23, 2017, 10:03am UTC](https://discourse.julialang.org/t/toward-faster-rationals/7933/6 "2017-12-23T10:03:13Z")
[https://github.com/timholy/Ratios.jl](https://github.com/timholy/Ratios.jl)
It’s not been extended beyond the simplest implementation, but might be a starting point.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [December 23, 2017, 10:27am UTC](https://discourse.julialang.org/t/toward-faster-rationals/7933/7 "2017-12-23T10:27:41Z")
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?
```julia
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
```
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [December 23, 2017, 10:28am UTC](https://discourse.julialang.org/t/toward-faster-rationals/7933/8 "2017-12-23T10:28:27Z")
or like that using variables as pointer handles
or like that … would using SVectors of length 2 be appropriate? @andyferris
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [December 23, 2017, 3:30pm UTC](https://discourse.julialang.org/t/toward-faster-rationals/7933/9 "2017-12-23T15:30:12Z")
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 `FastRational`s to include a param for either of two teleological Val{} types and use that to properly select dispatch before runtime.
---
### Author:  [@andyferris](https://discourse.julialang.org/u/andyferris)
#### Post date: [December 24, 2017, 1:38am UTC](https://discourse.julialang.org/t/toward-faster-rationals/7933/10 "2017-12-24T01:38:45Z")
`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.