## Interval Datatype

This page has a few interesting looking papers. I stumbled here because of the paper titled "A universal characterization of the closed Euclidean interval" (PDF)*. It contains a simple categorical definition of a notion of closed
interval that has computational content.

I want to point out the paper "Synthetic topology for data types and classical spaces" (PDF) on the above page. It describes itself roughly as "topology for computer scientists and computer science for topologists".

* The google search term I was using was actually "essential geometric morphism" which I was looking up with regards to topos theory and synthetic differential geometry.

## Comment viewing options

### Interval arithmetic is incredibly cool

Interval-based computations are really remarkably cool and powerful. I've implemented them in my programming language Frink and I have to say that there are few other programming constructs that have given me such a feeling of newfound power. The last time I had such a feeling of "wow, that'll make lots of things easier" was when I first learned about regular expressions in Perl over a decade ago.

For those not familiar with intervals, it's essentially a "new type of number" with upper and lower bounds, like [3, 5]. You can think of an interval as either representing an uncertain value within that range or as simultaneously taking on all values in that range, in a bit of quantum magic.

Here's the Frink documentation on interval arithmetic.

Why is it so cool? Well, sometimes it creates a ridiculously simple solution to difficult problems, like the rather difficult problem of graphing arbitrary equations. Can you write a program to graph both simple relations like y=sin[x] and, say, the circle x^2 + y^2 = 1 ? How about solid areas, or discontinous functions? Well, using interval arithmetic, it's easy. For example, here's the source of a simple Frink web-based application to graph arbitrary equations. You can also try it here.

All it does is treats each "pixel" as an interval, and tests to see if both sides of the equation may possibly be equal in that interval (using the "PEQ" possibly-equals operator). Neat!

I'm now fully convinced that every language should contain support for interval arithmetic. It can be done as an external library, but if it's well integrated into the fundamental numerical types, one can often feed a program normal numbers or intervals with absolutely zero code changes, which gives amazing power and flexibility.

### Is this a feature?

a = new interval[-2,3]
[-2, 3]

a^2
[0,9]

a*a
[-6,9]


Aziz,,,

### It's not a bug

Aziz, good question, and good test! In fact, that's a Frequently Asked Question in interval arithmetic. In short, no, it's not a bug. That's intended behavior, and is the way that all concrete interval arithmetic implementations that I know of work. Consider a variation of your example:

 a = new interval[-2,3] b = a a*b 

Which does exactly what it should and gives the bounds [-6, 9] as above.

Note that the bounds for the a*a case contain the bounds for the a^2 case. Both are correct, depending on whether you treat the variables as being independent or not. (I treat them as independent, as do all interval arithmetic implementations that I know.) However, the bounds for the latter case are "tighter", and thus preferable.

As I mentioned before, you can think of an interval as simultaneously taking on all values in a range, in which case the above behavior may make more sense, and you can and, in fact, must treat expressions like the above as being independent.

One should understand that arithmetic on intervals is not distributive. (It's usually called sub-distributive.) It matters what order you perform operations in. That is, a*(b+c) may give tighter bounds than ab+ac. Performing operations one way may give tighter bounds than if performed in another way, as above. Both answers are strictly correct, and one set of bounds will contain the other, but you usually want to write your calculations in a way that gives you the tightest possible bounds.

One should symbolically reduce equations as much as possible so the fewest number of intervals are used in any calculation in order to get the tightest bounds. Thus, a^2 is preferred to a*a.

Thus, in interval arithmetic, x/x does not necessarily equal 1. You should symbolically simplify your equations to give tighter bounds if this is the intent.

I'd recommend reading this article, most especially the "gotchas" section on page 5 for more examples of how interval arithmetic varies from normal math on real numbers. It answers your question directly.

See a FAQ here for related issues, like "does a - a = 0 or what?"

### doesn't that mean that as

doesn't that mean that as soon as you have the same variable occuring twice in your plot example, things go wrong? for example sin(x)/x.

### sorry, i should be less

sorry, i should be less cryptic - it seems to me that many (all?) non-trivial cases where intervals are interesting, they are interesting because there are dependencies. if everyone assumes that they are independent, is it really that useful?

also, can these be related in any useful way to error intervals? typically with errors you assume gaussian distributions and the "interval" represents the spread but is not a formal upper/lower bound. it's also common to assume that linear approximations are sufficient for calculations, so if you want to know the error in f(x) and have a known error in x then you can estimate the error in f(x) as df/dx * error(x). is a similar approximation used in interval handling? (this handles repeated variables "correctly")

### hmmm. slowly the gears in my

hmmm. slowly the gears in my head grind on. so is there some kind of unifying concept that makes intervals, error estimates, etc, all different instances of the same kind of phenomenon?
[edit (instead of another reply) - i guess if i read the leader article that might answer this.... sorry, was just replying to comments; edit 2 - and it's an interesting paper!]

### Error analysis vs. interval analysis

Interval analysis is similar to error analysis, but they're different in significant ways. Interval analysis will always give you the absolute most pessimistic error boundaries, (which is what an engineer might like to see,) and treats all variables as being possibly correlated, while traditional error analysis more often than not (but not necessarily) treats errors as uncorrelated and adds errors as, say, the shorter Pythagorean distance sqrt[error(x)^2 + error(y)^2].

If your error analysis treats all errors as being correlated, interval analysis will give identical results, assuming a proper formulation. Well, at least to the point that interval analysis always gives a "hard" containing bound, while most traditional error analysis gives a confidence interval.

There are lots of really nice properties to interval arithmetic that make it readily implementable in a programming language, though, as opposed to standard error analysis.

### Can these be related in any useful way to error intervals?

A better way to do this is with automatic differentiation which is like interval arithmetic but in the limit as the intervals become small. This discussion seems to have fissioned now but I talk about this here. It's similar to interval arithmetic in many ways but simpler to implement and it executes faster. Suitable modification allows you to compute multiple sensitivities simultaneously. It's much more efficient than doing symbolic differentiation. For example CFD people are able to use this approach to compute sensitivities of entire fluid simulations this way without having to repeatedly run the sim to compute finite differences. There's a web site here.

There are many ways to implement automatic differentiation. Some involve literally transforming your source code by differentiating it line by line. But my favourite approach is the one that looks a lot like interval arithmetic (which could also, in principle, be carried out by a source to source transformation).

### Not wrong, maybe just overestimated

One of the largest issues in the use of interval arithmetic is the common problem of "overestimation." This means that, as I noted above, with one formulation, some of your bounds may be larger than they would be if you formulated the problem another way.

There's a large body of work in this area of the field; in fact it's probably where most of the work goes--to make bounds as tight as possible but no tighter!

For example, your example of sin[x]/x, which is common in communication theory, is often redefined as a special function sinc[x] which has the special property that its value at 0 is exactly 1, (by a limit argument,) not undefined. It might be that in evaluating this, you'd be better to take the Taylor series for sin[x], which is:

sin[x] = x - x^3/3! + x^5/5! - x^7/7! + ...

And recast that as:

sinc[x] = 1 - x^2/3! + x^4/5! - x^6/7! + ...

Which symbolic reformulation might give significantly tighter bounds than if you wrote it the first way and then divided by x. Smarter, tighter estimates can also be made by analyzing the behavior of the derivatives of a function, and assuming that all instances of x in the equation are identical, for instance. The bounds for transcendental functions like sin[x] are even tighter than a naive Taylor series formulation due to clever analysis of this sort.

Minimizing error bounds in interval arithmetic is a bit of an art, and explains why mathematicians make the big bucks.

### seems to have problems

First off, that frink page doesn't actually define the operations, it just gives examples so it's a bit hard to make comments. This paper gives some definitions.

One should symbolically reduce equations as much as possible so the fewest number of intervals are used in any calculation in order to get the tightest bounds. Thus, a^2 is preferred to a*a.

Symbolic reduction is subject to certain rules and with interval arithmetic the rules are very different to numerical arithmetic. This quote suggests that we should reduce an expression using the rules of numerical arithmetic before evaluating it using a completely different (incompatible) set of rules. This sounds like a recipe for bugs and confusion, especially if you have a very smart optimising compiler that might perform some further "harmless" reductions.

Also, what is the point of the power operator? Why would you want [-2, 3]^2 = [0, 9]. You say it depends on whether you think of the intervals as being independent or not. So for the square operator we imagine starting at the left and moving to the right, squaring everything. That's fine and having dependent intervals could be a good thing however you propose no way of declaring intervals to be dependent, so there's no way for me to say A*B and by the way A and B are dependent. So you should either throw away A^2 != A*A or you should make it possible to express (in)dependence. For example if we allow intervals to have identity and we assume dependence for identical objects and independence for non-identical (although possibly equal) objects and allow scalar operations to preserve dependence

A=[-2, 3]
A^2 = [0,9]
A*A=[0,9]
A+A = [-4, 6]
A-A = [0,0]

B=[-2,3]
A*B=[-6, 9] # as they are independent
C = 2 * A # [-4, 6] linked to A
A*C = [0, 18] # == 2 * A*A == 2 * A^2
D = copy(A) # D has the same bounds as A but is no longer dependent
A*D = [-6, 9]


I think then the value of an expression would be independent of whether algebraic reductions had been performed or not (although I haven't worked through the details).

Basically there's not much point in allowing dependence for just a single operation, either disallow it completely or expand it to *, +, - and /.

Alas I have a feeling that successfully expanding it to all operations requires that the language has a symbolic maths engine inside.

Finally, it might be useful to expand the set of intervals. I presume [1,2]/[-1, 1] currently dies with the equivalent of divide by 0. If you allowed interval complements, so for example ]1, 2[ is all numbers except those between 1 and 2 then

[1,2]/[-1, 2] == ]-1, .5[


This has the interesting result that it becomes very easy to arrive at the whole line because ]-1, .5[ + [x + 0, x + 1.5] == everything for any value of x.

While interval arithmetic might be useful, I think that trying to wedge it into a language via overloading of arthmetic operators does not seem like a great idea, existing code using these operators contains many unstated assumptions about distrubivity, cancellation, comparability etc so simply pumping intervals into it and expecting it to work seems hopeful to say the least.

### The usual suspects

You've addressed a lot of the common issues and frequently asked questions with interval analysis. I might again point to an Interval FAQ to address some of these issues.

First off, that frink page doesn't actually define the operations, it just gives examples so it's a bit hard to make comments.

True, I don't define the operations as well as I'd like (but then I don't define addition over real numbers nor define things like sin[x] either.) I do follow the normal conventions of the field, though, so a standard text on interval analysis should discuss these. Some conventions are interesting, and subject to various implementations, such as for arctan[x] over intervals, which I should document more.

Symbolic reduction is subject to certain rules and with interval arithmetic the rules are very different to numerical arithmetic. This quote suggests that we should reduce an expression using the rules of numerical arithmetic before evaluating it using a completely different (incompatible) set of rules.

I think the difference in the rules is somewhat overstated here. I wouldn't characterize the rules as necessarily being completely different or incompatible, but I also see and agree with your point. If the mathematical analyst reduces the expression x/x to 1, they do so knowing that the variable is dependent and identical, so this is often entirely valid under the rules of real analysis or interval analysis. (In practice, the mathematician should almost always make these and similar cancellations when performing symbolic manipulation, even when working with intervals.) However, to be as safe as possible, Frink treats them as independent and thus gives wider bounds. It does require some human-level intelligence to make this decision, though, just like writing any numerical code. A smarter programmer can tighen the bounds, just as they can improve accuracy in a numerical calculation by reformulating an expression.

This sounds like a recipe for bugs and confusion, especially if you have a very smart optimising compiler that might perform some further "harmless" reductions.

Very true. Which is why Frink doesn't perform possibly-incorrect optimizations of this sort. (I, say, removed the early optimization that x/x=1 when introducing interval arithmetic.) In contrast, Mathematica has some potential issues in their interval analysis, as they perform their tree-rewriting rules to simplify expressions early on. I've seen cases where this could be considered to cause theoretical problems, especially in older versions of Mathematica, which had some absolutely disastrous bugs in their interval implementations early on.

Also, what is the point of the power operator? Why would you want [-2, 3]^2 = [0, 9].

This is simply the convention in the field, and gives the tightest possible bound, assuming a dependence that you maybe shouldn't assume in x*x. You should also note that the power operator can take intervals and/or floating-point numbers as either the base or exponent, which makes defining it essential for completeness.

I think that your points about symbolic reduction and the concept of identity of x/x and x-x are good, common questions, and possibly best addressed in the FAQ entries cited before. In short, I think most (all?) designers of interval libraries leave the decision to symbolically reduce an expression up to the programmer or numerical analyst, otherwise they assume independence, which is the safest possible tactic. It would be nice to express dependence/equivalence in code, though, and let the computer do some of the harder algebraic work when possible. I just don't know a language that does this reliably, though.

Finally, it might be useful to expand the set of intervals. I presume [1,2]/[-1, 1] currently dies with the equivalent of divide by 0.

Yes. It does currently die with a divide by zero error. This is one of the largest sources of diversity in interval arithmetic implementations. There are lots of different tactics to take when dividing by an interval containing zero, such as returning the union of two disjoint intervals, throwing an exception, having half-infinite intervals, using some sort of "containment set" behavior, having intervals with exclusions as you suggested, having undefined behavior, and so on. There's no good agreement to the best tactic to take, as you'll see if you survey various implementations. Right now Frink just flags an error and terminates. This behavior may change.

While interval arithmetic might be useful, I think that trying to wedge it into a language via overloading of arthmetic operators does not seem like a great idea, existing code using these operators contains many unstated assumptions about distrubivity, cancellation, comparability etc so simply pumping intervals into it and expecting it to work seems hopeful to say the least.

Heh. You do see the difficulties easily. :) These are well-known objections, but the rules that Frink and most other interval implementations have chosen are intentionally chosen to avoid cancellation and distributivity errors by giving the widest possible bounds. Still, though, converting real-valued code to interval-valued requires thought and has potential pitfalls.

Whenever possible, I try to help the programmer avoid potential pitfalls. For example, see the section of my documentation about Interval Comparison Operators, which transparently works with intervals if your calculations are unambiguous, but explicitly stops you if your calculations contain ambiguity.

You might be interested in some of the good FAQ entries about converting real-valued code to interval code. Here's a short one and an excellent longer one. They say it better than I can, especially the latter, and point out lots of dangers and good advice.

Overall, you have the same questions and objections that I had when first encountering interval analysis. Your questions are right on target, and very commonly encountered in the field.

### Interval Resources

By the way, if you're looking for more references on intervals and a survey of their use in different programming languages and libraries, I recommend this Interval Computations website.

### intervals and monte carlo calculations?

Very interesting indeed. In the financial industry tihs would be very useful for pricing some instruments. One (overy simple) example might be the following:
A $10 stock may be change its price by 10 cents, so tomorrow it might be$9.50 or $10.10. The day after it might move by max of 10 cents again, so the price might be between$9.80 and \$10.20 and so on. At the same time interest rate might be moving by max of 20 cents up or 10 cents down. What will be the price of an option on this stock one month out? (obviously, I left out some parameters, but making these kinds of calculaitons will make life easy for a very large number of people).

This is not exactly a problem of simple intervals, the 'interval' of a security price diverges with time, and the divergence may not be linear, but some way of easily expressing this problem would be wonderful :)

### Monte Carlo, baby!

I almost wrote this in my original post, but ran out of time. Monte Carlo analysis is one area where interval arithmetic becomes quantumagically cool.

A typical example is electrical circuit simulation. In a real circuit, all of your parts may have varying tolerances, say, your resistors will be 100 ohms plus or minus 10%. Your circuit may or may not behave well if certain components are at the limits of their tolerances, or too hot or cold.

The usual way to analyze this is to perform a monte carlo analysis; the values of each component are varied randomly, and you run the circuit over and over again to see if any combination of values causes unwanted behavior.

The number of cases that you need to analyze grows exponentially. Say, you have a circuit with 20 components, each with 2 varying parameters (e.g. for a transistor, it might be operating temperature and gain.) In order to analyze this circuit solely at the limit points for each component, you actually have to make 4^20 runs, or over a trillion runs! If the components' response is not monotonic, you have to run even more!

With interval analysis, it's possible to perform the same analysis in one run, giving you the worst possible behavior case, including all bounds and nonlinearities! Now that's as close as you'll get to a magical quantum computer in this decade!

The general problem is that error bounds may be overestimated, and it may be a bit difficult to formulate the problem. But, if your error bounds come out tight enough, you know that your circuit will behave properly in all regimes. If the bounds come out large, you can then decide how much more work you want to do.

### I'm not an expert but aren't

I'm not an expert but aren't you a bit overstating the benefits of IA?
If the function is non-monotonous, then things becomes a little more complicated for interval analysis no?
Or is-this included in the 'may be difficult to formulate the problem' provision?

### Significance arithmetic

Steve Richfield had Monte Carlo methods in mind, among others, when he proposed "significance arithmetic" as a simple way of tracking accuracy of a result: see numerous threads on comp.arch.arithmetic.

### I guess I should have said this immediately

This is not (directly) about interval arithmetic, rather it is closer to exact real arithmetic (for example), and, related to a recent thread, can be used as an intuitionistic approach to dealing with real numbers.

The datatype in the paper is (slightly modified to be more Haskelly):

data I = -1 | 1 | M (Nat -> I)

Two functions are defined on it corresponding to the two universal properties they mention. These actually happen to be simply the unfold function for streams (Nat -> I is equivalent to a stream) and the natural fold function for the above data type. In fact, to make it clearer write,

newtype Stream a = Cons a (Stream a)

we then have the (paramterized) unfold,

unfoldStream :: (a -> b) -> (a -> a) -> (a -> Stream b)
unfoldStream hd tl x = Cons (hd x) (unfoldStream (hd . tl) tl x)

and

mapStream :: (a -> b) -> Stream a -> Stream b
mapStream f (Con hd tl) = Cons (f hd) (mapStream f tl)

then the interval data type is,

data I = -1 | 1 | M (Stream I)

with the fold,

foldI lo hi m -1 = lo
foldI lo hi m 1 = hi
foldI lo hi m (M s) = m (mapStream (foldI lo hi m s))

Their corec function is,
corec hd tl x = M (unfoldStream hd tl x)

### vaguely related to the

vaguely related to the original topic, here's a paper on Computing over the Reals: Foundations for Scientific Computing from the AMS.

(apologies if this has been posted already - i dont read everything and know i duplicated a link earlier in the interval arithmetic thread)