current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 2 down vote favorite

Let $k\in \mathbb{N}$ be fixed. The naive way to compute a sequence of values $a_1^k,\ldots,a_n^k$ where $a_i\in \mathbb{N}$ for all $1\leq i\leq n$ is compute $a_i^k$ individually with the exponentiation by squaring. This takes a total of $O(n\log k)$ multiplications.

Is this optimal? What if for each $a_i$, we have $\frac{1}{c} a_i \leq a_{i+1}\leq c a_i$.

I come up with this question because I was doing a binary search over $f(n)=n^k$.

share|improve this question
1  
Why is the number of multiplications optimal if $a_{i+1} = a_i^k$? –  C. Brand Aug 13 '13 at 8:24
    
If you know that $a_{i+1} = a_i^k$ then we have to find just value of $a_n^k$ which means is $O(n+\log k)$. –  user742 Aug 13 '13 at 14:01
    
I was wrong, thanks for point it out. That is actually the best possible situation... –  Chao Xu Aug 13 '13 at 17:34
    
You can also try $a^b = \exp(b\log a)$ if you don't need exact results. –  Yuval Filmus Aug 13 '13 at 18:07
    
There are various methods for batch exponentiation that use fewer multiplications than the obvious method. They have been studied in the cryptography literature; you might explore the crypto literature on speeding up exponentiation. Cryptographers study exponentiation mod p, so you might need to check whether all of their speedups also apply over the integers as well. –  D.W. Aug 14 '13 at 4:46
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.