0
$\begingroup$

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$

  • 0
    Sorry but I have not understood the question. What do you want to do?2012-07-25
  • 1
    He wants $x=z^{\lfloor \log_z y\rfloor}$2012-07-25
  • 0
    @ThomasAndrews Thanks! Now the question is clear :-)2012-07-25

2 Answers 2

1

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.

  • 0
    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.2012-07-25
  • 0
    @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)...2012-07-25
  • 0
    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.2012-07-25
  • 1
    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).2012-07-25
  • 0
    Please excuse my limited exposure to mathematical notations. Should I interpret your answer as: z*(log(y)/log(z))?2012-07-25
  • 1
    @RaheelKhan: z to the power of floor of quotient of the two logarithms power(z,floor(ln(y)/ln(z)))2012-07-25
  • 0
    $\lfloor w \rfloor$ is the largest integer smaller than or equal to $w$2012-07-25
1

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