In SICP there’s a fairly long extended exercise in interval arithmetic. I strongly recommend going and reading, both for the maths and the lisp.
Besides being good for the soul, a question opens up as to whether interval arithmetic is a good idea, and if it is, then why isn’t it generally implemented?
We’ve all seen it – a bug which we’ve had to chalk up to rounding error.
Floating points are all fine and dandy, but in the modern age, couldn’t we get around it? Besides the ad-hoc interval arithmetic in SICP, there is a formal proposal for such a system called Unums – so why aren’t we using interval arithmetic generally?
1 There is No ‘Perfect’ Representation
You’re thinking that floating point algebra is just an approximation to something better. You’re sick of typing in one divided by two and seeing 0.499999999. If I have to approximate, then why not track the approximation?
For one thing – you can track fractional numbers perfectly. Store them as pairs of integers. If you’re worried about the size of your integers – most languages have a arbitrary size integer implementation. Done – perfect fractions. The whole of the rational numbers bend to your will.
Except life isn’t rational.
There’s √2, π, e all waiting on the next street corner to beat you up.
Fine. Add in all the algebraic numbers (anything that’s the solution of a polynomial expression) – that covers all the √’s.
Add π, e, and all it’s combinations.
You haven’t even begun to cover the irrational numbers.
They’re literally uncountable – you can’t even start to list them.
The best you can do is model ones that you’re interested in, which should be enough for most. What numbers are important to you?
2 Intervals Don’t Behave
Add two intervals – you add the lower bounds, you add the upper bounds. Sorted.
- Add (1 +/- 0.05) to (2 +/- 0.01)
- Answer is (3 +/- 0.06)
So far so good. Subtraction, makes sense, as does division and multiplication. In each case your looking for the range of the answer, what’s the biggest the answer could be, what’s the smallest the answer could be.
Except – what about division again?
- Divide (2 +/- 0.1) by (0.1 +/- 0.2)
- Naively, looking at the endpoints:
- At one end we have 2.1 / 0.3 = 7.0
- At the other end we have 1.9 / (-0.1) = -19.0
- Which is a respectable interval : -19 to +7.0
But look again:
- Let’s pick some other endpoints:
- 2.1 / (-0.1) = -21.0 – Outside our first naive interval.
- It gets worse – let’s not even try an end-point
- 2.0 is within the first interval.
- 0.01 is within the second interval.
- 2.0 / 0.01 = 200.0 – well outside the naive answer!
- It gets even worse
- The second interval contains zero.
- Hence the division explodes to infinity over the interval.
SICP recognizes this, and suggests that division is modified so that it throws an error if it covers a zero. Which is fine.
The problem in general is whether it’s easy to recognize these cases.
- Suppose you have a function f(x) = ( 1 / (1-2x) )
- Is it obvious what a ‘bad’ value for x is?
- Suppose you have a function g(x) = (1 / 0.2 + (sin 4x))
- Is it obvious what a bad value for x is?
- Suppose you have a function h(x) = tan (1 + 7x)
- Is it obvious what a bad value for x is?
Your interval arithmetic library is probably going to throw an exception somewhere – but it will probably be up to you to find out where the problem is.
3 Intervals Aren’t Psychic
- 5 – 5 = ?
In normal arithmetic, the answer is fairly neatly zero. Suppose we have an interval. Solve:
- (5 +/- 0.01) – (5 +/- 0.01) = ?
There are at least two answers:
- Exactly 0
- 0 +/- 0.02
Before you dismiss one, consider the case in the original SICP problem set, where the numbers are resistors with some tolerance.
- What is the difference between two different 5 Ohm resistors, each with +/- 0.01 Ohm tolerance?
- (5.0 +/- 0.01) – (5.0 +/- 0.01) = 0 +/- 0.02 Ohms
- In the extreme case one is 5.01, and the other is 0.49.
- If I have a circuit with a 5 Ohm resistor, and then I remove the 5 Ohm resistor, what is the remaining resistance?
- (5.0 +/- 0.01) – (5.0 +/- 0.01) = 0 Ohms exactly
- Regardless of the tolerance of the resistor, the resistor has been removed – it doesn’t leave a ‘tolerance hole‘!
So two different situations, both sensibly represented by the same expression, but having different meanings.
As a more complex but practical example, I worked for some time with a company that attempted to predict the timing properties of silicon chips. The path any signal takes through a chip has some variation, a particular path in the circuit will sometimes be slightly faster, sometimes slightly slower, based on what’s going on in the circuit. A key question becomes then:
- If I need two signals at a certain point for a calculation, what’s the maximum time that I’ll need to wait from the first signal for the second to arrive?
- Let’s say that they set off at the same time.
- Ideally I’d like them to arrive at the same time. But lets be pessimistic, lets assume one signal runs as fast as it could, and the other as slow as it could. That’ll give me a good bound for the difference in arrival between the two signals.
So far so good – but sometimes the signals shared part of their paths. And it’s easy to observe that a path can’t be both fast and slow at the same time. i.e. For those common parts of path we shouldn’t include a variation. And this correction was significant for the calculations being performed, a lot of effort was spent trying to eliminate this ‘extra’ error that was incorrectly added.
In summary, my point is that interval arithmetic cannot be a drop in solution.
- For almost all cases, floating point arithmetic is good enough.
- In cases where it’s not, you need to be careful about edge cases – and as you move away from trivial operations the edge cases become more and more complex.
- If you’re using something other that than a scalar number, you probably need to decide why and what it means.
In the cases where it’s not enough, the programmer needs to understand the problem domain in order to handle errors in a meaningful fashion. An interval library should not be a drop in solution, but the engineer needs to understand the limit of the model.
- What do interval operations mean? What are they modelling?
- How important is it to keep intervals ‘tight’?
- How important is it to detect divide by zero errors?
As always, spend some hammock time, understand the problem, and then write something awesome.