Up

# Nested Intervals

When talking about nested intervals, people often refer to the idea of taking an interval as a starting point and approximating a value by making the interval closer over a specifc amount of iterations.

Note that the next interval always has to be contained in the previous interval, and thus the intervals get arbitrarily small over time.

To get to know the possibilities of nested intervals a little better, why don't we try to approximate the value of π using them.

## Setup

First of all, we have to choose our initial interval.

As we do not want to pick the end by random, let's write a function that takes a given start point (in our case 0.0) and moves along the x-axis until cos(x) is below zero.

Because we started at x = 0.0 and we know that cos(0) = 1, we can conclude that we must have passed the x-axis, as stated by the Intermediate value theorem.

Also looking at the plotted graph, we know that starting at 0, cosine is a monotonically non-increasing function.

(setq step-width 0.2)
(defun find-end (start)
(setq e start)
(setq offset 0.0)
(while (= e start)
(setq value (cos (+ start offset)))

(if (< value 0)
(setq e (+ start offset)))

(setq offset (+ offset step-width))
)
e
)

Notice that I chose a step-width of 0.2, I could have gone with 1, but as we want to choose the lowest x possible (and we do not want to run into a monotonically non-decreasing section) I decided to go with a lower value.

Now that we are able to calculate the end point, let's quickly definte our interval boundaries:

(setq ts 0.0)
(setq te (find-end ts))
(print te)
- 1.5999999999999999


As you can choose our end point is approximately 1.6.

## The next step

Now that we defined our interval boundaries, we can write the function that modifies the interval.

The idea here is that we calculate cos(x), where x is in the middle of our interval. This is also where the fact that the cosine is monotonically non-increasing in our given interval comes into play: Because that way we know, that all values left of a given x are bigger that the value at the given point. And all values right of the given x are smaller.

Knowing this we can analyze the value of our center point, and if the resulting y value is bigger that 0, we know that we have to look on the right side, because we know that $cos({\pi \over 2}) = 0$ and we essentially want to find the spot where the cosine is equal to 0, because we know that, the point is equal to $\pi \over 2$ and we can use it to calculate the value of π.

(defun iter (start end)
(setq mid (/ (+ start end) 2.0))
(setq val (cos mid))
(cond
((> val 0) (list mid mid end))
(t (list mid start mid))
)
)

## Results

Now it is time to approximate π and to do that, we can write a small function that updates the interval boundaries after every step.

I already ran this function a couple of times, so I know that we have to run it 28 times for the first 8 decimal places to be correct: 3.14159265

(dotimes (i 28)
(setq intv (iter ts te))
(print (* 2 (car intv)))
(setq te (caddr intv)))
- 1.5999999999999999
- 2.4
- 2.8
- 3.0
- 3.0999999999999996
- 3.1499999999999995
- 3.1249999999999996
- 3.1374999999999993
- 3.1437499999999994
- 3.140624999999999
- 3.1421874999999995
- 3.1414062499999993
- 3.1417968749999994
- 3.141601562499999
- 3.141503906249999
- 3.141552734374999
- 3.141577148437499
- 3.1415893554687493
- 3.141595458984374
- 3.141592407226562
- 3.141593933105468
- 3.141593170166015
- 3.1415927886962884
- 3.1415925979614254
- 3.1415926933288567
- 3.141592645645141
- 3.141592669486999
- 3.14159265756607


## Speed

Before we finish todays article, let's talk about speed: As you can see from my example above, it took me 28 cycles to achieve an accuracy of eight decimal places.

This might seem like a lot at first, but the other option would have been to iterate through every single x value, and there are an infinite amount of them $[0,{\pi \over 2}] \in \mathbb R$. For example if we had chosen a step-width of 0.00000001, which would have been necessary to calculate the first eight decimal places, this would have taken us about 157 million iterations.

The reason why works so much better is that we essentially make the interval half as small in every iteration, resulting in logarithmic cost development.

## Conclusion

Nested intervals are an easy way to quickly approximate numbers, without complex calculations.

For example, Wikipedia also has an example of approximating $\sqrt{19}$. However you should keep in mind, that you are approximating the value and thus results may vary.