A brief introduction to interval arithmetic

Interval arithmetic powers this graphing calculator I made.

The user can enter a formula without solving for y, like “y^y = x^x”. I rearrange into “0 = x^x - y^y”. Then I use interval arithmetic to calculate the result interval of “x^x - y^y” for x = the x-axis range of the graph’s view, y = the y-axis range of the graph’s view. If the result interval contains 0 then I have something to draw. I recursively divide the ranges in half and do a binary search until I find very tiny intervals that contain solutions. I draw those as points on the graph.

Example formulas this can handle:

https://memalign.github.io/m/formulagraph/index.html?f1(x,t)...

This article does a great job at explaining interval arithmetic. However, the introduction says

>Instead of treating each as exactly 7 feet, we can instead say that each is somewhere between a minimum of 6.9 feet and a maximum of 7.1. We can write this as an interval (6.9, 7.1).

Yes we can use an interval to express an uncertainty. However, uncertainties in physical measurements are a little bit more complicated.

When I measure something to be 7 plus minus 0.1 feet, what I am saying is that the value of the measured variable is not known for sure. It can be represented by a bell curve centred on 7 and 95% of the area under the curve (95% probability) that the true value lies between 6.9 and 7.1. The value of the measured variable is much more likely to be 7 than 6.9. There is also a small chance that the value lies outside of the 6.9 to 7.1 range.

In an interval, there is no probability distribution. It is more like an infinite list of numbers.

In practice, interval arithmetic is seldom used for uncertainty analysis for scientific experiments.

This is a good article!

In ClickHouse, interval arithmetic is applied to index analysis. A sparse index consists of granules, and each granule is an interval of tuples in lexicographic order. This interval is decomposed into a union of hyperrectangles. Conditions such as comparisons, logic operators, and many other functions are evaluated on these hyperrectangles, yielding boolean intervals. Boolean intervals represent ternary logic (always true, always false, can be true or false). Interesting tricks include: applying functions that are monotonic on ranges (for example, the function "day of month" is monotonic as long as the month does not change), calculating function preimages on intervals, and even calculating preimages of n-ary functions, which is useful for space-filling curves, such as Morton or Hilbert curves.

Check for more details: https://github.com/ClickHouse/ClickHouse/blob/master/src/Sto...

Or see examples, such as https://adsb.exposed/

The article links to a "Gustafson vs Kahan" debate transcript. The video is more entertaining: https://youtube.com/watch?v=KEAKYDyUua4

>Instead of treating each as exactly 7 feet, we can instead say that each is somewhere between a minimum of 6.9 feet and a maximum of 7.1. We can write this as an interval (6.9, 7.1).

This is not how measurements work in physics. You have to measure at least twice (If you measure only once the sample variance will be infinite due to the bessel correction).

Only then you can compute the mean value of your measurements and the standard error. Assuming you made two measurements 6.9 and 7.1 you would write length = 7.0 +/- 0.1 . (see https://www.omnicalculator.com/statistics/standard-error?v=t... )

There are several ways to handle uncertainties and propagation of error. Interval arithmetic is one of the simpler methods. Some Python packages that focus on this problem:

https://pythonhosted.org/uncertainties/

https://pypi.python.org/pypi/soerp

https://pypi.python.org/pypi/mcerp

This last one is one of my favorite Python libraries. My hunch is that it is highly underrated.

I am still looking for/consider implementing error propagation as probability distributions where these are symbolic.

I've experimented on a few systems to apply interval arithmetic to type inference, i.e.

   // starRating is an int<0,5>, meaning
   // integer between 0 and 5 inclusive.
   let starRating = console.readInt<0,5>("How many stars do you rate this movie?");
   db.addStarRating(starRating);

   // starRatingList is a list<int<0,5>>
   let starRatingList = db.readStarRatings(movie);

   // totalStarRatings is an int<0,5*starRatingList.length>
   // this type can't be sized at compile time, but we can still check it!
   let totalStarRatings = sum(starRatings);

   // avgStarRating is a very difficult type, because we need to either have
   // a fraction type that's slow, or some handling of rounding/truncating
   // when we do division. So now we're dealing with 3 intervals: min/max,
   // min/max precision, and min/max error.
   let avgStarRating = totalStarRatings / starRatingList.length;

> Why x^2 isn't always x * x

It turns out he's claiming they're different if x^2 is interpreted as squaring each element in the interval x, while x * x is interpreted as a cross product: the interval obtained by multiplying all pairs of elements in the interval. But I haven't ever seen anyone use x^2 to mean pointwise squaring on an interval x. Is that some kind of standard notation?

> You measure the wall with a ruler and get 7 feet, then you measure the couch and get 7 feet. Can you fit the couch against that wall?

Normally, yes: the couches generally have somewhat squishy... stuffing? filling?.. which hang off the wooden frame, so you generally can squeeze a couch from the sides a bit to fit it into slightly narrower space.

> say 1/10th of a foot.

This is unholy. Either say "an inch" for this hypothetical scenario, or use some decimal-based measurement system.

Couldn't the overdetermination problem be solved by tagging intervals with their ids? E.g., "x*x" should be resolved as "(x, i[-3, 3])*(x, i[-3, 3])" and "i[-3, 3]*i[-3, 3]" as "(nil, i[-3, 3])*(nil, i[-3, 3])". Since the tag matches in the first expression and not in the second (nil != nil) different rules could be used.

Btw this comes up a lot in compiler design for dynamic languages since constraining the value ranges of variables means that you can implement them more efficiently. In static languages it is not as important since the domains of most variables are either given to you or inferred by the type system.

Also an interesting head scratcher is how to implement interval arithmetic for modulus: i[3,6] % i[3, 6] = ???*

I took the idea of interval types and decomposed them to an even lower primitive: Inequality types. An interval type is just an intersection of two inequality types. For example `(>0) & (<1)` is the interval `(0, 1)`. You can read this as "a number being larger than 0 and smaller than 1". `(<1)` is also valid, which is "a number smaller than 1" as a type.

The nice thing about this decomposition is that applying arithmetic "just works" because you just define them for the inequality primitive.

I prototyped this for TypeScript and created a proposal. It does not contain type-level arithmetic because TS doesn't do that kind of type-level stuff in general. I'm not entirely convinced myself of that proposal, but maybe someone finds this interesting:

https://github.com/microsoft/TypeScript/issues/43505

Great article!

you may be interested in the relationship between programmatic Junctions and Interval Arithmetic ...

a question in our Discord channel asked "why are arithmetic operations on Ranges restricted" with some examples like this:

  (1..2) + 3 => (4..5)   #ok
  (1..2) + (3..4) => 4   #not (4..6)!

to cut a long story short, I made the Math::Interval module to extend the Range class to provide a working Interval Arithmetic model that uses a Junctions of Ranges to represent disjoint results

  # a divisor that spans 0 produces a disjoint multi-interval
  my $j1 = (2..4)/(-2..4);
  ddt $j1;            #any(-Inf..-1.0, 0.5..Inf).Junction
  say 3 ~~ $j1;       #True

(The long story is at https://rakujourney.wordpress.com/2023/11/11/junctions-for-i...)

If you are curious about this then you might also want to have a look at "propagation of uncertainty".

https://en.wikipedia.org/wiki/Propagation_of_uncertainty (warning: contains math symbols)

One detail of interval arithmetic not mentioned in TFA but of much consequence in the context in which we have to contend with in Ardour is ...

When you ask if a single non-interval lies within a given interval, the answer is yes or no (with a given resolution).

When you ask what the relationship between 2 intervals is, there are multiple answers (*). In a given problem domain, each one may have different semantic implications.

(*)

  interval 1 is larger than interval 2 and fully includes it
  interval 2 is larger than interval 1 and fully includes it
  interval 1 begins before interval 2
  interval 1 ends after interval 2
  interval 2 begins before interval 1
  interval 2 ends after interval 1
  interval 1 and interval 2 are disjoint
  interval 1 and interval 2 are equivalent at a given resolution

The 68040 CPU had two rounding modes to support interval arithmetic.

From the M68040 User’s Manual (https://www.nxp.com/docs/en/reference-manual/MC68040UM.pdf):

"The processor supports four rounding modes specified by the IEEE 754 standard. These modes are: round to nearest (RN), round toward zero (RZ), round toward plus infinity (RP), and round toward minus infinity (RM). The RP and RM modes are directed rounding modes that are useful in interval arithmetic."

The real takeaway was the Frink language. https://frinklang.org.

The manual was a great read and the examples he uses are very entertaining.

See clpBNR with SWI Prolog for a way to use interval arithmetic in the broader scope of logic programming.

https://github.com/ridgeworks/clpBNR

Great job at explaining the complexities in this topic.

The x*x vs. x^2 issue that the author presents seems contrived. Interval arithmetic is just a specialized case of arithmetic on random variables. If two values are uncorrelated, why would you use the same variable for them? The ambiguity could be trivially resolved by representing the problem as x*x vs. x*y, where x = (3, 3) and y = (3, 3).

Aren't intervals a rather limited substitute for distributions (of error)? Using the intervals as if they and their joint distributions are uniform doesn’t make much sense to me. Perhaps if you really need to know the limits, but then as was mentioned elsewhere, the interval widths grow very quickly.

Why isn't it called "intervallic arithmetic", sounds kinda clunky

Using intervals for measurements has some limitations. But for many use cases we do not need more than intervals, so it's nice to have convenient tools for them. Intervals are a convenient model.

That's because measurements are complicated.

You use a ruler (or some other instrument) to measure something and get a value x.

You are happy.

Then for some reason you decide to repeat the measurement and you get a slightly different value. And problems start.

You decide to write down all the values you get. You are happy again.

Shortly after, you realise you have to use those values in calculations and you just want "one representative value", so you take the average or "the most common value" or some other aggregation, use your intuition!

Things start to go wrong when you have to take a decision by setting some threshold like "I do this if my value is above a threshold". Because the actual value may be different from your averaged number.

So you take the standard deviation and call it the uncertainty x±s.

But one day you realise that your measurements are not symmetric. You start by saying "instead of x±s, I will use different upper and lower bounds to define an interval".

For instance some things are measured on a log scale and you have a measure like 100±"one order of magnitude" which is "100, but may be between 10 and 1000".

Then you add a confidence, because you are not 100% certain you actually are in that range. Your measurement becomes "with 95% confidence I can say the measure is in [10,1000], with an expected value of 100".

Then you want to combine and aggregate those intervals and you realise they within the intervals their regions are not uniform, you actually have a probability distribution.

In the simple case is a Gaussian distribution, described with mean and variance. It can also be a binomial (a "p out of n cases" scenario). Or a lognormal like un our 10-1000 example.

And now for each measure you take you need to understand what probability distribution it follows and estimate its parameters.

And that parameter estimation is a measure, so it has confidence intervals as well.

At this point adding two measurements becomes not so easy anymore... But don't panic!

The nice part about all of this is that usually you don't care about precise error estimates, because you can live with bounding errors covering a worst case scenario.

And you can use the Central Limit Theorem (sometimes it is abused rather than used) to simplify calculations.

It is a rabbit hole and you need to know how deep you want to dig. Intervals are usually convenient enough.

How can this be generalised to the complex plane?