Calculating the number of times a value must be halved for it to be less than or equal to another value

This is not a homework question; I'm working out an algorithm for an app I'm writing and I want to calculate the number of times I must halve a base value for it to be less than or equal to a minimum. I can write the equation, but I have no idea how to start solving it.

I guess the equation looks like this:

$$\dfrac{y}{2^x} \leq z$$

Given some large value of $y$, e.g. $10000000$, and a minimum value for $z$, e.g. $1$, how do I find $x$?

With my example values, the equation would be:

$$\dfrac{10000000}{2^x} \leq 1$$

• The programmer in me says, that $y$ isn't very large :P and unless this calculation needs to be done extremely fast, you could just write a loop. Is $y$ an integer? Do you have guarantees as to its size in bits? – Ben Millwood Mar 24 '15 at 0:45
• Multiply both sides by $2^x$, then $y \leq 2^x \implies \log_2 y < x$ – user4894 Mar 24 '15 at 0:45

Hint: $\log_2$ is monotonically increasing.

Divide both sides by $z$ and relabel $\frac{y}{z}$ as $Y$. Then, rearranging gives $$Y \leq 2^x,$$ and by monotonicity we have $$\log_2 Y \leq \log_2 (2^x) = x.$$ Since "number of times" must be an integer, we need to double $\lceil \log_2 Y \rceil$ times, and since it must be nonnegative, we have $$x = \text{max}\{\lceil \log_2 Y \rceil, 0\}.$$

• How do you make the answer respond to mouseovers like that? – user4894 Mar 24 '15 at 0:50
• @user4894 Type >!foo . It's very useful for elaborating on hints, I think, so that OPs/others can try to work out the problem for themselves before reading the full details of an answer. – Travis Willse Mar 24 '15 at 0:53