rationals with unreal performance 𝓪
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.
- 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 exports types
FastRational{Int128} (FastQ128)andFastRational{BigInt} (FastQBig).-
FastQ128is 1.25x..2x faster thanRational{Int128}when using appropriately ranged values. -
FastQBigwith large rationals speeds arithmetic by 25x..250x, and excels atsumandprod. -
FastQBigis best with numerators and denominators that have no more than 25_000 decimal digits.
-
| 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.
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)
Up to 25_000 digits, FastRational{BigInt}s FastQBigInt handily outperform Rational{BigInt}s in arithmetic calculation.
When applied to appropriate computations, FastQBigInts often run 2x-5x faster. These speedups were obtained evaluating
The Bailey–Borwein–Plouffe formula for π
at various depths (number of iterations) using Rational{BigInt} and FastRational{BigInt}.
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.
sumandprod
| 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.
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.
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.
| 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.
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.
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
- There is no
FastRationalrepresentation for Infinity - There is no support for comparing a
FastRationalwith NaN
Klaus Crusius has contributed to this effort.
This work stems from a discussion that began in 2015.
The rational compactifying algorithm paper is in the ACM digital library.
𝓪 Harmen Stoppels on 2019-06-14