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

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

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jun 18, 2015 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
    Commented Jun 18, 2015 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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