## FastRationals.jl

Arithmetic with small and with very large rationals is made fast.
Author JeffreySarnoff
Popularity
19 Stars
Updated Last
5 Months Ago
Started In
December 2017

# FastRationals.jl

## 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)` and `FastRational{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)` and `FastRational{BigInt} (FastQBig)`.

• `FastQ128` is 1.25x..2x faster than `Rational{Int128}` when using appropriately ranged values.

• `FastQBig` with large rationals speeds arithmetic by 25x..250x, and excels at `sum` and `prod`.

• `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
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 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}`.

#### 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` and `prod`
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

The calculation of these magnitudes appears here.

### 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_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

Context Rather Than State

what slows FastRationals

the `mayoverflow` predicate

## 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 2019-06-14

### Required Packages

View all packages