# Finding the closest number to the power of 2 for x.

What is the fastest way to calculate x given y as a large integer?

$y = 100$
$z = 2$
$x = 64$ (Power of z and smaller than or equal to y).

$x = f(100, 2) = 64$
$x = f(128, 2) = 128$
$x = f(90, 3) = 81$

-
Sorry but I have not understood the question. What do you want to do? – Romeo Jul 25 '12 at 21:20
He wants $x=z^{\lfloor \log_z y\rfloor}$ – Thomas Andrews Jul 25 '12 at 21:22
@ThomasAndrews Thanks! Now the question is clear :-) – Romeo Jul 25 '12 at 21:23

If you want to avoid a loop you may use : $$\displaystyle x=z^{\lfloor\frac{\ln(y)}{\ln(z)}\rfloor}$$

else multiply $1$ by $z$ until being greater than $y$ and return the previous value.

-
You can do better than looping - first keep squaring, until $z^{2^n}>y$. Then use binary search to find power between $2^{n-1}$ and $2^n$. You can use that you've already computed $z^2$,$z^4$,... to make your binary search faster. – Thomas Andrews Jul 25 '12 at 21:24
@ThomasAndrews: Hmmm Shouldn't the first solution be faster in this case? The loop is useful for $y$ small or reduced floating point library. We could too make a lookup table and so on (anyway I supposed that the OP wanted the log formula you proposed too)... – Raymond Manzoni Jul 25 '12 at 21:31
Yeah, I was just saying it was better than "... else multiply by z until being greater than y and return the previous value," which takes $O(\log_z(y))$ multiplications. – Thomas Andrews Jul 25 '12 at 21:32
For powers of two we may shift 2^16, 2^8 and so on or use bit masks (say for a long) f & 0000FFFF and then f & 00ff00ff, f & 0f0f0f0f and so on (5 iterations instead of 32). – Raymond Manzoni Jul 25 '12 at 21:35
@RaheelKhan: z to the power of floor of quotient of the two logarithms power(z,floor(ln(y)/ln(z))) – Raymond Manzoni Jul 25 '12 at 21:38

$$\huge x= z^{\lfloor (\log_z y) \rfloor}$$

What this means is you take the largest integer which is less than the logarithm base z of y. (this is the largest integer power you can raise z to get a number smaller than or equal to y) raise z to this power to get x.

-