Reals and Order

What else do I need to put into Babel-17 v0.3 to be able to use it in real-world projects? As a prerequisite for things like graphics, floating point arithmetic is highest on my wish list.

So I want to add a new type real. But the thing is, I never liked the way floating point was usually treated in programming languages. When working on my diploma thesis and especially when working on my PhD, what I needed wasn’t mere floating point arithmetic, but interval floating point arithmetic.

Babel-17 will be radical in its treatment of floating point arithmetic: there will be only interval arithmetic. Interval arithmetic is just so obviously superior to ordinary floating point arithmetic that this decision is a no-brainer. The only theoretical reason against interval arithmetic I can think of is the dependency problem: when you evaluate an expression in which the same variable occurs several times, interval arithmetic will often overestimate the error. For example, the expression

x - x

will yield something non-zero if x is an interval of width greater than zero. Therefore,

1.0/3.0 - 1.0/3.0

will never be zero when doing classical interval floating point arithmetic.

But in my opinion this is not a problem at all. First, in order to reduce the error introduced by dependencies, just make your interval bounds tighter. Second, in case this is not good enough for your application and you really need x - x to evaluate to zero, you probably shouldn’t do floating point arithmetic at all, but rather turn to computer algebra.

A practical problem with interval arithmetic is that it is not very well supported on many platforms. For example in Java, it is downright impossible to implement a performant implementation of interval arithmetic that calculates bounds as tight as the underlying hardware would support it. But again, this just means that your intervals will be a little wider than they could be. Also, Babel-17 implementations that compile directly to machine code can circumvent most of these problems.

Introducing interval arithmetic into Babel-17 has ripple effects. The main reason for this is the ordering imposed on intervals. The most appropriate order seems to be defined via

[a; b] <= [c; d] iff (b < c or (a = c and b = d))

There are other orders of interest like inclusion of intervals, but the above seems to be the right choice for the canonical order of intervals.

Unfortunately, there is no way that such an interval type together with this order could currently be defined in Babel-17. Of course I could implement special magic for reals, and the importance of this particular type would justify such a special treatment; but it still feels odd and I just don’t like such a resolution of the problem.

Another thing to consider is the interplay between integers and reals. Once you start using special magic, you would definitely expect to allow the comparison of integers and reals. But this leads to results a naive user might be unprepared for, like

2 == 4.0 / 2.0

not being true (depending on how the particular interval arithmetic implementation works). Let’s face it: It is just not a good idea to compare integers and reals. If you want to do this, do it by explicitly converting between integers and reals.

Extending the above discussion, one might also ask: Is it a good idea to canonically compare lists with vectors? And, is it a good idea to canonically compare values of different types at all? I think the answer is no. Those parts of Babel-17 relating to order, I definitely need to rework them.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: