# 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\}.$$