fractional_arithmetic.md

fractional_arithmetic.md

Fractional Arithmetic

When we represent numbers as fractions of integer numerator and denominator, we can perform arithmetic on these fractions. This is useful for situations where we wish to work with fractional values, but need lossless results, something that floating point encoding can not always guarantee.

We represent a fractional number as a tuple of two integer values, separated by a slash:

a / b = (v#0 / v#1) = V

Here, v#0 is mapped to a, while v#1 is mapped to b. Variables of fractional type use upper case letters, while variables of integer or real type use lower case letters.

While the numerator v#0 can take take on any integer value, the denominator v#1 is constrained to any non-zero integer value in this encoding. When v#1 is zero, then the value of v#1 decides on a special value:

v#0 / 0 = 
  if (v#0 >=  1)  infinity
     (v#0 <= -1) -infinity
     (v#0  =  0)  NaN

An integer or real value can easily be converted to fractional using a desired denominator n >= 1:

x = ((x * n) / n)

For real values, n controls the fractional precision of the stored value. The higher n is (limited by the integer type's maximal width, which is typically 32 or 64 bits), the higher the precision with which the fractional part of the real value is stored. It is suggested though to use low denominators when building new fractions, as we will soon see.

The fractional value V can be be converted back to a single lossy real value (typically named float or double in most languages) using:

x = real(v#0) / real(v#1)

Equalizing the denominators of two fractions is required for some operations. For two fractional values U and V, u#1 and v#1 can be equalized by sharing a factor:

U' = ((u#0 * v#1) / (u#1 * v#1))
V' = ((v#0 * u#1) / (v#1 * u#1))

Repeated equalization can easily lead to integer overflows. One must either be careful about its use, or frequently normalize fractions before further processing. It is also advised to not equalize when u#1 and v#1 are already equal.

To normalize a fraction V, an integer factor s common to numerator and denominator must be found (typically the greatest common divisor), where

v#0 % s = v#1 % s = 0

Then the fraction can be losslessly normalized using e.g.

s = gcd(v#0, v#1)
normalize(V) = ((v#0 / s) / (v#1 / s))

Finding a common divisor grows increasingly less trivial the higher the divisor is. Managing the prime divisors in circulation then is a good way to speed up guesses.

Two fractional values U and V can be directly compared when the denominators have been equalized, for which there is a shortcut, as the denominators do not need to be compared:

U ? V = (u#0 * v#1) ? (v#0 * u#1)

The same applies to addition and subtraction.

U + V = ((u'#0 + v'#0) / u'#1) = ((u#0 * v#1 + v#0 * u#1) / (u#1 * v#1))
-V = (-v#0 / v#1)
U - V = U + (-V) = ((u'#0 - v'#0) / u'#1) = ((u#0 * v#1 - v#0 * u#1) / (u#1 * v#1))

Multiplication, reciprocal and division require no equalization.

U * V = ((u#0 * v#0) / (u#1 * v#1))
1 / V = V^-1 = (v#1 / v#0)
U / V = U * (1 / V) = ((u#0 * v#1) / (u#1 * v#0))

Here's how to apply powers and square roots with removal of radicals. When the result is real, a coefficient n >= 1 can be used to select the desired precision.

V^x = ((v#0 ^ x) / (v#1 ^ x))
sqrt(V) ~= ((sqrt(v#0) * n) / (sqrt(v#1) * n)) ~= ((sqrt(v#0) * sqrt(v#1) * n) / (v#1 * n))

Rounding:

floor(V) = v#0 / v#1
ceil(V) = -floor(-V)

Modulation:

U % V = U - V * floor(U / V)

Lastly, how to obtain sign, absolute value, and positive denominator:

|V| = (|v#0| / |v#1|)
sign(V) = sign(v#0) * sign(v#1)
absdenom(V) = ((v#0 * sign(v#1)) / |v#1|)

Ever heard of FRACTRAN?..