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.

  • $\begingroup$ "0 to 8" implies $n=3$ ($2^3=8$). The middle mark at $x=4$ should be 3 units high, those at $x=2$, $x=6$ two units, those add odd $x$ one unit. (Nothing is explicitly stated about marks at 0 and 8, where the ruler ends.) $\endgroup$ Sep 11, 2012 at 8:29
  • $\begingroup$ @HagenvonEitzen What I didn't understand is scaling from 1/(2 to power of n) inches to n, n-1 and so on? $\endgroup$ Sep 11, 2012 at 8:35

2 Answers 2


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  
             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.)

  • $\begingroup$ There is no need to go recursive. If you think about it, it's pretty easy to deduce how long the mark at a number $i$ should be, and then just do a for-loop. $\endgroup$
    – Arthur
    Sep 11, 2012 at 8:52
  • $\begingroup$ @Arthur: That’s true, but it would not surprise me at all if the assignment were intended as an exercise in recursion. However, I’ve modified the wording to be less definite. $\endgroup$ Sep 11, 2012 at 8:53
  • $\begingroup$ @BrianM.Scott: thanks for explanation. I taught increase the height as we move futher but that is not the case in this, so in this case height of marking doesnot say anything about distance from 0. Am I right? As you mentioned this topic is from recursion. $\endgroup$ Sep 11, 2012 at 9:00
  • $\begingroup$ @venkysmarty: It does not tell you what the distance from $0$ is, but it does have something to do with it. Look at the original marked points at $1/8,1/4,3/8,1/2,5/8,3/4,7/8$, written as fractions in lowest terms, and compare the denominators with the heights of the marks; do you see the relationship? $\endgroup$ Sep 11, 2012 at 9:03
  • $\begingroup$ @BrainM.Scott: Yes there is relation ship. Thanks for explanation. $\endgroup$ Sep 11, 2012 at 10:33

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.