Successive Interval Halving

In a previous post I talked about the trapezium rule for approximating integrals. One nice feature was that one can successively increase the resolution without having to evaluate the function at points at which it has already been evaluated once. The formula I gave was

If one uses this method from the onset, this will result at the function being evaluated at the following points

Step i	y = (x − a) / (b − a)
0	0
1	1
2	1/2
3	1/4
4	3/4
5	1/8
6	3/8
7	5/8
8	7/8

and so on. A few days ago I was creating a demonstration and I wanted to create a longer table with these values. I didn't want to create it by hand so I was looking for a closed formula that produces the values in the second column from those in the first column. After some pondering over the problem I came up with the following formula

Here the denotes the floor function, i.e. the largest integer that is smaller or equal the argument. This formula will produce all the numbers in the table, including the zero, but not the one. The one, therefore, still has to be added by hand. Usually I would advise against using logarithms and exponentials in numerical algorithms but, because they are to the base 2, they can be implemented by bit shifting operations.

There is actually an interesting relation between 2n + 1 and y when we write them as binary numbers. In fact, if we write 2n + 1 as binary and place a decimal point after the leading 1 we get y + 1. Here is an example

2n+1	100111012
y+1	1.00111012
y	0.00111012