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: