Rationalising Denominators 4: Ratios

Posts in this series:

Powers

Products

Sums

Ratios

Roots of unity

Rationalising denominators

Introduction

So far we’ve represented numbers using:

• Power, which raises an integer value to a Fractional exponent
• Product, which contains a list of Power values
• Sum, which contains a list of Product values

In this post, we introduce a Ratio of two Sum values, which is the most expansive numerical representation in this series (if you want to go even further, you might like my Ivory Tower library, which is very much a work-in-progress at the moment!)

Ratios

Our initial implementation is simply a tuple of two values, representing the numerator and denominator. We’ll forbid zero as a denominator, since that isn’t well-defined:

def Ratio(numerator: Sum, denominator: Sum) -> Tuple[Sum, Sum]:
    assert denominator != sum_zero

    # 0/n normalises to 0/1
    if numerator == sum_zero:
        return (sum_zero, sum_one)

    return (numerator, denominator)

I’ve also added a simple normalisation step for Ratio values whose numerator is zero: since every such Ratio is equivalent (they are all the number zero), we make their representations the same by replacing their denominators with the number one.

Arithmetic With Ratios

Here are some useful constants:

ratio_zero = Ratio(sum_zero, sum_one)
ratio_one = Ratio(sum_one, sum_one)
ratio_neg = Ratio(sum_neg, sum_one)

Addition and multiplication are defined as usual for fractions:

def add_ratios(r1: Ratio, r2: Ratio) -> Ratio:
    n1, d1 = r1
    n2, d2 = r2
    return Ratio(
        add_sums(multiply_sums(n1, d2), multiply_sums(n2, d1)),
        multiply_sums(d1, d2)
    )

def multiply_ratios(r1: Ratio, r2: Ratio) -> Ratio:
    n1, d1 = r1
    n2, d2 = r2
    return Ratio(multiply_sums(n1, n2), multiply_sums(d1, d2))

Normalising to lowest terms

In this post we’ll only cover one part of the normalisation process: reducing to lowest terms, by removing common factors. Since our Product representation is already broken down into prime factors, we can perform this normalisation by removing those factors which occur in every term of the numerator and denominator. We already saw in the previous part how to find the common_factors_of_sum, so we just need to extend our Ratio function to find and remove common factors from the numerator and denominator:

def Ratio(numerator: Sum, denominator: Sum) -> Tuple[Sum, Sum]:
    assert denominator != sum_zero

    # 0/n normalises to 0/1
    if numerator == sum_zero:
        return (sum_zero, sum_one)

    # Find common factors in the numerator and denominator
    num_factors, _ = common_factors_of_sum(numerator)
    den_factors, _ = common_factors_of_sum(denominator)
    common_product = Product(*{
        base: min(exp, num_factors[base])
        for base, exp in den_factors.items()
        if base in num_factors
    }.items())

    # Remove common factors from top and bottom of ratio
    return (
        remove_common_product(numerator, common_product),
        remove_common_product(denominator, common_product)
    )

Normalising negation

There is another redundancy in our Ratio representation, since a value like -x/y is equivalent to x/-y, e.g. 1/√1 = √1/1. In fact, a Sum value may contain positive and negative terms, so we count those up to produce an overall “signum” (number of positive terms minus number of negative terms; assuming that 0 terms have already been discarded during normalisation):

def sum_signum(s: Sum) -> int:
    return sum(
        {True: -count, False: count}[
            dict(irrational).get(1, zero) >= half
        ]
        for irrational, count in s.items()
    )

We can switch between these equivalent forms by negating the numerator and denominator (multiplying by √1/√1 = 1); and will choose our normal form to be whichever has the highest denominator signum (i.e. the “more positive” denominator). If they match, we’ll pick the highest numerator signum; and if those match as well, we’ll fall back to just comparing the terms lexicographically:

def r_complexity(r: Ratio):
    num, den = r
    # Negate the signums, so "more positive" values get a "smaller" complexity
    return (-sum_signum(den), -sum_signum(num), s_items(den), s_items(num))

We can use this in Ratio, to pick whichever of the two forms has the lowest complexity:

    given = (numerator, denominator)
    negated = (
        multiply_sums(numerator, sum_neg),
        multiply_sums(denominator, sum_neg),
    )
    return negated if r_complexity(negated) < r_complexity(given) \
        else given

Normalising recursively

Since our Ratio function is performing multiple simplification steps, the order that we perform those steps becomes important; since earlier steps may rely on transformations that are only performed by later steps. We can avoid such problems by having Ratio call itself recursively whenever a normalisation step has altered the representation; and hence only finish once none of the steps are able to simplify any further.

However, there’s a problem: the negating step we just defined speculatively negates the numerator and denominator; if we try to recursively normalise that then its own negating step will negate them again, recursing with the original value we started with! To avoid this infinite loop, we’ll set a flag called negating in this case, and only perform the speculative check when that flag isn’t set:

def Ratio(numerator: Sum, denominator: Sum, negating=False) -> Tuple[Sum, Sum]:
    assert denominator != sum_zero

    # 0/n normalises to 0/1
    if numerator == sum_zero:
        return (sum_zero, sum_one)

    # Find common factors in the numerator and denominator
    num_factors, _ = common_factors_of_sum(numerator)
    den_factors, _ = common_factors_of_sum(denominator)
    common_product = Product(*{
        base: min(exp, num_factors[base])
        for base, exp in den_factors.items()
        if base in num_factors
    }.items())

    # Remove common factor, if it's not trivial
    if common_product not in [product_one, product_neg]:
        # Divide-through by common factor
        return Ratio(
            remove_common_product(numerator, common_product),
            remove_common_product(denominator, common_product),
            negating=negating,
        )

    # Finally, try negating the whole thing (unless we've already done so) and
    # seeing if that's simpler.
    given = (numerator, denominator)
    negated = given if negating else Ratio(
        multiply_sums(numerator, sum_neg),
        multiply_sums(denominator, sum_neg),
        negating=True
    )
    return negated if r_complexity(negated) < r_complexity(given) \
        else given

Conclusion

In this post we’ve introduced a Ratio type. With this, we can finally represent fractions like ½. This may seem rather convoluted, considering that we started with Fraction right at the beginning (for the exponent of a Power). Alternatively, we could have supported fractions if we allowed our exponents to be negative, but we instead explicitly forbade them. Indeed, negative exponents would behave perfectly reasonably, and work nicely with our normalisation algorithms! The reason we do not allow such things is that they make it hard to split values into a numerator and a denominator, which we’ll require for the final part of this series. In contrast, this Ratio representation makes it trivial!

The reason we’re not quite finished is due to a problem involving fractional powers (i.e. roots), which break our assumptions regarding divisibility and factoring. For example, consider the value 1/(1 + √2): if we multiply its numerator and denominator by the same non-zero value, we should get back the same result (since that’s equivalent to multiplying by 1). However, if we try that using 1 + √1√2 we’ll find ourselves with the value (√1 + √2)/1.

That must be equal to value 1/(1 + √2) we started with; but they do not have the same representation, which shows that we do not yet have a normal form. To fix this, we need an algorithm called “rationalising the denominator”, which this whole series has been building to!

However, we still need to cover a little more background before we get there, which will be covered in the next post

The full code for this post is available in the fraction_ratios module of my conjugate repo.