1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – Ben Millwood Mar 24 '15 at 0:45
  • $\begingroup$ Multiply both sides by $2^x$, then $y \leq 2^x \implies \log_2 y < x$ $\endgroup$ – user4894 Mar 24 '15 at 0:45
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ How do you make the answer respond to mouseovers like that? $\endgroup$ – user4894 Mar 24 '15 at 0:50
  • $\begingroup$ @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. $\endgroup$ – Travis Willse Mar 24 '15 at 0:53

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.