Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
Sorry but I have not understood the question. What do you want to do? –  Romeo Jul 25 '12 at 21:20
1  
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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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
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). –  Raymond Manzoni Jul 25 '12 at 21:35
1  
@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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.