FastRationals.jl
rationals with unreal performance ^{𝓪}
Copyright © 20172019 by Jeffrey Sarnoff. This work is released under The MIT License.
FastRationals
additional functionality
FastRational types
System rationals reduce the result of every rational input and each arithmetic operation to lowest terms. FastRational types (FastQ32
, FastQ64
, FastQBig
) reduce all rational inputs and reduce each rational value prior to presenting the value. Unlike system rationals, the result of a FastRational arithmetic operation is reduced only if overflow occur while it is being calculated. With appropriately sized numerators and denominators, this takes less time.
FastRationals using fast integers
 These types use fast integers :
FastRational{Int32} (FastQ32)
andFastRational{Int64} (FastQ64)
.  Arithmetic is 12x..16x faster and matrix ops are 2x..6x faster when using appropriately ranged values.
These FastRational
types are intended for use with smaller rational values. To compare two rationals or to calculate the sum, difference, product, or ratio of two rationals requires pairwise multiplication of the constituents of one by the constituents of the other. Whether or not it overflow depends on the number of leading zeros (leading_zeros
) in the binary representation of the absolute value of the numerator and the denominator given with each rational.
Of the numerator and denominator, we really want whichever is the larger in magnitude from each value used in an arithmetic op. These values determine whether or not their product may be formed without overflow. That is important to know. It is alright to work as though there is a possiblity of overflow where in fact no overflow will occur. It is not alright to work as though there is no possiblity of overflow where in fact overflow will occur. In the first instance, some unnecessary yet unharmful effort is extended. In the second instance, an overflow error stops the computation.
FastRationals using large integers

FastRationals exports types
FastRational{Int128} (FastQ128)
andFastRational{BigInt} (FastQBig)
.
FastQ128
is 1.25x..2x faster thanRational{Int128}
when using appropriately ranged values. 
FastQBig
with large rationals speeds arithmetic by 25x..250x, and excels atsum
andprod
. 
FastQBig
is best with numerators and denominators that have no more than 25_000 decimal digits.

performance relative to system rationals
computation  avg rel speedup 

mul/div  20 
polyval  18 
add/sub  15 
mat mul  10 
mat lu  5 
mat inv  3 

avg is of FastQ32 and FastQ64

polynomial degree is 4, matrix size is 4x4

This script provided the relative speedups.
Rationals using BigInt
harmonic numbers
using FastRationals
n = 10_000
qs = [Rational{BigInt}(1,i) for i=1:n];
fastqs = [FastQBig(1,i) for i=1:n];
qs_time = @belapsed sum($qs);
fastqs_time = @belapsed sum($fastqs);
round(qs_time / fastqs_time, digits=2)
(I get 17x)
25_000 decimal digits
Up to 25_000 digits, FastRational{BigInt}s FastQBigInt
handily outperform Rational{BigInt}
s in arithmetic calculation.
When applied to appropriate computations, FastQBigInt
s often run 2x5x faster. These speedups were obtained evaluating
The Bailey–Borwein–Plouffe formula for π
at various depths (number of iterations) using Rational{BigInt}
and FastRational{BigInt}
.
what works well
The first column holds the number of random Rational{Int128}s used
to generate the random Rational{BigInt}
values that were processed.
These relative performance numbers are throughput multipliers.
In the time it takes to square an 8x8 Rational{BigInt} matrix,
thirty 8x8 FastRational{BigInt} matrices may be squared.
sum
andprod
n rationals  sum relspeed 
prod relspeed 

200  100  200 
500  200  350 
 matrix multiply and trace
n rationals  mul relspeed 
tr relspeed 

64 (8x8)  15  10 
225 (15x15)  20  15 
This script provided the relative speedups.
what does not work well
Other matrix functions (det
, lu
, inv
) take much, much longer. >> Fixes welcome <<.
Meanwhile, some matrix functions convert first convert FastRationals to system rationals,
compute the result, and reconvert to FastRationals.
Most performant ranges using fast integers
FastRationals are at their most performant where overflow is absent or uncommon. And vice versa: where overflow happens frequently, FastRationals have no intrinsic advantage. How do we know what range of rational values are desireable? We want to work with rational values that, for the most part, do not overflow when added, subtracted, multiplied or divided. As rational calculation tends to grow numerator aor denominator magnitudes, it makes sense to further constrain the working range. These tables are of some guidance.
________ FastQ32 ______________________________ FastQ64 __________
range  refinement  range  refinement  

±215//1  ±1//215  sweet spot  ±55_108//1  ±1//55_108 
±255//1  ±1//255  preferable  ±65_535//1  ±1//65_535 
±1_023//1  ±1//1_023  workable  ±262_143//1  ±1//262_143 
±4_095//1  ±1//4_095  admissible  ±1_048_575//1  ±1//1_048_575 
The calculation of these magnitudes appears here.
additional functionality
rational compactification
compactify
(rational_to_compactify, rational_radius_of_indifference)
From all rationals that exist in the immediate neighborhood^{𝒃} of the rational_to_compactify, obtains the unique rational with the smallest denominator. And, if there be more than one, obtains that rational having the smallest numerator.
using FastRationals
midpoint = 76_963 // 100_003
coarse_radius = 1//64
fine_radius = 1//32_768
tiny_radius = 1//7_896_121_034
coarse_compact = compactify(midpoint, coarse_radius) # 7//9
fine_compact = compactify(midpoint, fine_radius) # 147//191
tiny_compact = compactify(midpoint, tiny_radius) # 76_963//100_003
abs(midpoint  tiny_compact) < tiny_radius &&
abs(midpoint  fine_compact) < fine_radius &&
abs(midpoint  coarse_compact) < coarse_radius # true
^{𝒃} This neighborhood
is given by
±_the radius of indifference_, centered at the rational to compactify.
enhanced rounding
FastRationals
support two kinds of directed rounding, one maintains type, the other yields an integer.
 all rounding modes are available
RoundNearest
,RoundUp
,RoundDown
,RoundToZero
,RoundFromZero
> q = FastQ32(22, 7)
(3//1, 3//1)
> round(q), round(q, RoundNearest), round(q), round(q, RoundNearest)
(3//1, 3//1, 3//1, 3//1)
> round(q, RoundToZero), round(q, RoundFromZero), round(q, RoundToZero), round(q, RoundFromZero)
(3//1, 4//1, 3//1, 4//1)
> round(q, RoundDown), round(q, RoundUp), round(q, RoundDown), round(q, RoundUp)
(3//1, 4//1, 4//1, 3//1)
> round(Integer, q, RoundUp), typeof(round(Integer, q, RoundUp))
4, Int32
> round(Int16, q, RoundUp), typeof(round(Int16, q, RoundUp))
3, Int16
what is not carried over from system rationals
 There is no
FastRational
representation for Infinity  There is no support for comparing a
FastRational
with NaN
more about it
acknowledgements
Klaus Crusius has contributed to this effort.
references
This work stems from a discussion that began in 2015.
The rational compactifying algorithm paper is in the ACM digital library.
^{𝓪} Harmen Stoppels on 20190614