drawing markings on a ruler

Question

Let us consider the simple ask of drawing the markings on a ruler. Each inch on the ruler has a mark at the $1/2$ inch point, slightly shorter marks at $1/4$ inch intervals, still shorter marks at $1/8$ inch intervals, and so forth. Our task is to write a program to draw these marks at any given resolution, assuming that we have at our disposal a procedure $\operatorname{mark}(x,h)$ to make a mark $h$ units high at position $x$.

If the desired resolution is $1/2^n$ inches, we rescale so that our task is to put a mark at every point between $0$ and $2^n$, endpoints not included. Thus, the middle mark should be $n$ units high, the marks in the middle of the left and right halves should be $n-1$ units high, and so forth.

My questions on above text are

I do not understand how author rescaled middle mark should be $n$ units high if desired resolution is $1/2^n$ inches ?

How is the first paragraph is related to second paragraph?

Please explain with simple example like I want to mark at every point between $0$ and $8$.

Thanks for your time and help.

Answer 1

Take your example of $n=3$. If we were really marking at a resolution of $1/2^3=1/8$ inches, we’d mark $1/8,1/4,3/8,1/2,5/8,3/4$, and $7/8$ (since we’re not marking the endpoints at $0$ and $1$ inches). To make matters simpler, we’re going to rescale this by multiplying everything by $8$, so that our interval will be from $0$ to $8$ instead of from $0$ to $1$, and the marks will come every inch, instead of every $1/8$ inch.

If $n$ were $4$, the original problem would be to mark the interval from $0$ to $1$ inch in increments of $1/16$ inch: $1/16,1/8,3/16,1,4$, and so on up to $15/16$. To avoid the fractions, we would multiply everything by $2^4=16$ and cover the interval from $0$ to $16$ instead, marking $1$-inch intervals instead of $1/16$-inch intervals.

The marking itself is fairly simple. The mark in the middle is to be of height $n$; if $n=3$, that will be a mark $3$ units high at $x=4$. Then we look at the left interval, from $x=0$ to $x=4$, and the right interval from $x=4$ to $x=8$, and find the midpoint of each; these midpoints are $x=2$ and $x=6$, and they get marks of height $n-1=2$. Keep going in this manner; in the case of $n=3$, there’s only one more stage, and it produces marks of height $1$ at $x=1,3,5$, and $7$. Here’s a rough sketch:

                                     x  
                         x           x           x  
                   x     x     x     x     x     x     x  
             |-----------------------------------------------|  
             0     1     2     3     4     5     6     7     8

The idea is probably for you to design a recursive algorithm that takes as input the ends of an interval and a height, finds the midpoint of the interval and draws a mark of the desired height, and then calls itself for the left and right subintervals surrounding that mark. If you’ve learned anything about traversing trees, you may want to think about that, too. (Of course, it can also be done without recursion, and my guess about that may be wrong.)

Answer 2

Assume your ruler is $2^n$ units long. The height of the mark at the point $k$, where $0<k<2^n$, depends on the number of ending zeros in the binary representation of $k$: the more zeros, the higher the mark should be. Odd numbers have no zeros at the end, and get a mark of height $1$. The number $2^{n-1}$, which is the midpoint of the ruler, has $n-1$ zeros at the end, and will therefore get a mark of height $n$.

From this observation we deduce the following rule: For any $k$, where $0<k<2^n$, the height of the mark at $k$ is one more than the number of ending zeros in the binary representation of $k$.