2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Why is the number of multiplications optimal if $a_{i+1} = a_i^k$? $\endgroup$ – Cornelius Brand Aug 13 '13 at 8:24
  • $\begingroup$ 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)$. $\endgroup$ – user742 Aug 13 '13 at 14:01
  • $\begingroup$ I was wrong, thanks for point it out. That is actually the best possible situation... $\endgroup$ – Chao Xu Aug 13 '13 at 17:34
  • $\begingroup$ You can also try $a^b = \exp(b\log a)$ if you don't need exact results. $\endgroup$ – Yuval Filmus Aug 13 '13 at 18:07
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Aug 14 '13 at 4:46
1
$\begingroup$

In the worst case, this seems to be optimal. If your $a_i$ are pairwise coprime, e.g. $k$ different primes, they powers do not share any factors.

Of course, if $k$ is large but $c$ from your proposed restriction is small, there may not be such a set; then, you powers share factors. You could exploit this if you knew the shared factors for your $a_i$; but finding those is harder than just computing all the powers.

So I daresay, no, you can not do this faster without more knowledge about the $a_i$.

$\endgroup$
  • $\begingroup$ Finding the shared factors can be done with GCD, which (depending on how big $k$ is) could be faster than computing the powers. In the case the $a_i$ are coprime you could compute (a_i * a_{i+1})^k and then reduce mod $a_{i+1}$ or mod $a_i$ to get either $a_{i+1}^k$ or $a_i^k$ but that is not any faster either. $\endgroup$ – Tom van der Zanden Jun 18 '15 at 13:03
  • 1
    $\begingroup$ @TomvanderZanden True, GCD is sufficient for some speedup. I thought you'd have to factor the $a_i$, but that's not strictly necessary. That said, the probability that the $a_i$ are set-wise coprime is quite high. $\endgroup$ – Raphael Jun 18 '15 at 13:14

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.