# Spigot, and rational approximations

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.