# Spigot, and rational approximations

Posted on by Chris Warburton

I recently came across spigot (via lobste.rs). It’s available in Nixpkgs via the `spigot` attribute.

## Computable numbers

Spigot is a calculator, which claims to work with “exact real numbers”; but I find that terminology rather confusing, since almost-all “real numbers” cannot be described or represented (not just by spigot, but even in principle). Instead I would say spigot works with the computable numbers: those which can be approximated to arbitrarily-small error.

## On-going and never-ending representations

Consider the number ⅓: this has a simple representation as a rational number (i.e. as one whole number divided by another), but attempting to write it as a decimal requires approximation with some amount of error: e.g. 0.3, or 0.33, or 0.333333333, etc. If we allow the decimal places to go on arbitrarily far, our approximation will get an arbitrarily-small error. To represent ⅓ as a decimal “exactly” would require a never-ending sequence of threes. We can’t write down such a sequence directly, so we need to use a more expressive language that can describe the pattern followed by those digits. I’ll use the Bash language, which can represent ⅓ “exactly” like this:

``printf '0.'; while true; do printf '3'; done``

This is a generalisation of finite decimals, since we can always append a never-ending suffix of zeros to the latter. Spigot can consume and produce such on-going decimals, but it can’t see or understand their “source”; so it doesn’t actually know it’s dealing with ⅓. For all spigot knows, some other digit could appear at some point.

Despite characterising these numbers as “decimal”, Spigot also works with other natural-number bases: for example, we can write ⅓ in dozenal as 0.4. However, no matter which base we choose, there will always be rational numbers that can’t be represented with finitely-many places (e.g. dozenal can’t represent ⅕ exactly).

### Rational approximants

Rational numbers are independent of any particular base, and hence a more “fundamental” way to represent non-whole numbers. One downside is that it’s not obvious how to extend them to the sort of on-going approximation we can get with decimals; since the value of the numerator and denominator are coupled.

One rather brute-force approach is to generate an on-going sequence of separate rational numbers. Spigot can output such sequences, but doesn’t support reading them; presumably because there’s no way to ensure such sequences will actually converge to something.

### Continued fractions

Continued fractions are a generalisation of rational numbers, which allow on-going, never-ending generation and ensure convergence. Spigot supports reading and writing continued fractions.

## The downside

Tools like Spigot allow correct, “exact” arithmetic on a huge space of useful numbers. Yet they come with a major downside: equality becomes undecidable! It’s interesting that we can perform arithmetic with numbers yet not compare them, but the reason is simple: it can require information from arbitrarily-far along the sequence. For example, consider an on-going decimal which begins like 0.3333…; is this equal to ⅓? If it’s not equal to ⅓, then one of its decimal places must have a digit other than 3, and Spigot will eventually find that discrepancy and tell us that they’re not equal. Yet comparing numbers which are equal will never finish (making equality “semi-decidable”)!

## Bounds and boundaries

Internally, Spigot represents each number with an upper- and lower-bound, both rational. It outputs the next digit, continued-fraction, etc. once these bounds agree on that prefix. For example, if our result is known to sit in the interval between 123/1000 and 124/1000, we can output 0.12 with confidence; then wait for the bounds to get closer before committing to any more digits.

There is a famous problem with this approach, caused by boundaries in the representation. For example, we cannot output any digits of 0.0000… - 0.0000…, since we don’t know if it’s positive, negative or neither; e.g. the following outputs nothing, even with the `-c` option for continued fractions:

``````spigot 'base10fd:3 - base10fd:3' \
3< <(printf '0.'; while true; do printf '0'; done)``````

Unfortunately the sequence of rational convergents (option `-C`) also doesn’t output anything, since it’s based on the continued fraction. This is a shame, since Spigot does have rational bounds, which could be used to generate approximants directly (rather than going through the continued fraction). For example, it could output a rational `x/y` for the largest `y` such that the upper bound is below `(2x+1)/2y` and the lower bound is above `(2x-1)/2y`; i.e. when we can confidently round to the nearest `1/y`. Here’s how we can approximate the above example, as more and more digits are read in:

• 0.… - 0.… is between `0 - 1 = -1/1` and `1 - 0 = 1/1` inclusive (remember that 0.9̇ = 1). The least-precise rational we could form is `0/1`, but that’s only valid for the interval strictly between `(2×0+1)/2 = 1/2` and `(2×0-1)/2 = -1/2`, which is tighter than our bounds so far. Hence we can’t output any rational approximation yet.
• 0.0… - 0.0… is between `0 - 0.1 = -1/10` and `0.1 - 0 = 1/10`, which is between `1/2` and `-1/2`, so `0/1` would be a valid approximation. However, we can be even more precise, since those bounds are also in `(-1/4,1/4)`, `(-1/6,1/6)` and `(-1/8,1/8)`, so `0/2`, `0/3` and `0/4` are also valid approximations. `0/5` is not, since its interval is `(-1/10,1/10)`; since we’re not including the end-points, that’s strictly tighter than our bounds. The largest denominator gives the most precise approximation, so we should output `0/4`.
• 0.00… - 0.00… is between `-1/100` and `1/100`, so it can be approximated by `0/49`, to the nearest `1/49`.
• 0.000… - 0.000… can be approximated by `0/499`, to the nearest `1/499`
• and so on, with the denominator of the most precise approximation being one less than half the next power of 10.