3
$\begingroup$

Given $(U,V)$ two integers of finite size, I have a question about the complexity of calculating the $V^U$, i.e. $V$ raised to the power $U$. Is their a polynomial time algorithm to do this? If not is this an NP-hard problem?

$\endgroup$
  • 1
    $\begingroup$ see cs.stackexchange.com/questions/37242/… $\endgroup$ – Ran G. Jun 4 '15 at 0:42
  • $\begingroup$ @RickDecker I vaguely remember there was a very good answer for this question (probably by Yuval?) but couldn't found it myself. Also was too lazy to do the right thing (as you did!) and properly answering it.. $\endgroup$ – Ran G. Jun 4 '15 at 3:25
  • 1
    $\begingroup$ What research have you done? This is covered in standard textbooks and in Wikipedia. What complexity model? Number of basic operations (additions, multiplications, etc.)? Number of bit operations? $\endgroup$ – D.W. Jun 4 '15 at 19:16
6
$\begingroup$

One way to do this is by repeated squaring. First, express $V$ in binary, $$ V = b_0+2^1b_1+2^2b_2+2^3b_3+\dotsm+2^nb_n $$ where each $b_i$ is either zero or one. Having done this, repeatedly square $U$ to get $U, U^2, (U^2)^2 = U^4, (U^4)^2=U^8, \dotsc, U^{2^n}$. Then $$\begin{align} U^V&=U^{b_0+2^1b_1+2^2b_2+2^3b_3+\dotsm+2^nb_n}\\ &=(U^{b_0})((U^2)^{b_1})((U^4)^{b_2})\dotsm((U^{2^n}))^{b_n}) \end{align}$$ For example, to compute $3^{21}$ we would get the binary expansion of $21=16+4+1$ and then repeatedly square the $3$s:

$$\begin{align} 3^1 &=3\\ 3^2 &=9\\ 3^4 &=81\\ 3^8 &=81^2=6561\\ 3^{16} &= 6561^2=43046721 \end{align}$$ So we'll have $$ 3^{21}=3^{16+4=1}=(3^{16})(3^4)(3^1)=(43046721)(81)(3)=10460353203 $$ Consider the worst case, with $V=2^n-1$, and let $d$ be the number of bits in the representation of $U$. This will require $n-1$ squarings. Let's use the grade-school multiplication algorithm, for which the product of two $k$-bit numbers will take $O(k^2)$ primitive operations. We'll then have $$\begin{array}{ccc} \text{product}& \text{factor size} & \text{ops needed}\\ U^2 & d & d^2\\ U^4 & 2d & 4d^2\\ & \dotsc & \\ U^{2^{n-1}} & 2^{n-2}d & 4^{n-2}d^2 \end{array}$$ So the total number of operations needed to precompute the squares will be $$ (1+4+4^2+\dotsm+4^{n-2})d^2 = O((2^n)^2d^2) = O(V^2\log^2U) $$

Now since we chose $V$ so that it involved all of the squares we computed, we'll have the final product $(U)(U^2)(U^4)\dotsm(U^{2^{n-1}})$. Mirroring the construction above, we find that the final product will also take $O(V^2\log^2U)$ operations, so to compute $U^V$ by repeated squaring will take time $(2^nd^2)$ where $n, d$ are the number of bits in $V$ and $U$, respectively. Unfortunately, this means that this construction is not polynomial in the size of $V$.

Notes.

  1. In your original question, strictly speaking, the classes P, NP, Np-complete and NP-hard are generally applied to decision problems, which this isn't.
  2. There are faster ways to compute the product of two integers, so you can actually do better than $O(V^2\log U)$.
  3. While this (as it turns out) is actually less efficient than the naive algorithm of computing $U^V$ by successive multiplications, $U, U^2, U^3,\dotsc$, it works very well when computing modular powers, $U^V\pmod W$, since none of the intermediate products will ever be larger than $W$.
$\endgroup$
  • $\begingroup$ Thanks a lot. I just need a clarification for what you mean by "primitive operations". When they define polynomial time problem set $P$, do they say what are those primitive operations? This has always confused me. $\endgroup$ – seek Jun 4 '15 at 2:11
  • $\begingroup$ @seek. When we talk about primitive operations, we generally mean those that are essentially close to being at assembly-level, namely adding two bits or multiplying two bits. A level up would be evaluating $x<y$ for two binary numbers. This isn't quite primitive, since it would either be implemented as "subtract $x$ from $y$ and check that the result is positive or negative" or doing a comparison of the bits in the numbers, either one of which could take $O(n)$ for $n$-bit numbers. Remember, in this (log-cost) model, the numbers involved may be arbitrarily large, so we need to be aware of that $\endgroup$ – Rick Decker Jun 4 '15 at 2:20
  • $\begingroup$ I'm not buying this. It is true that this uses $O(\log U)$ multiplications, but with repeated squaring the numbers get larger with each step and you cannot really assume that every multiplication will take $O((\log V)^2)$ operations. For example, is it really true you can compute $2^N$ with $O(\log N)$ operations, while the result takes $N$ bits to write? $\endgroup$ – sdcvvc Jun 4 '15 at 15:18
  • $\begingroup$ @sdcvvc. Quite right. Again, I learned the truth of the maxim "Post in haste, repent at leisure". My only excuse is that it was late at night and I must have been fuzzy. I've edited my post to be closer to correct. $\endgroup$ – Rick Decker Jun 4 '15 at 18:13
  • $\begingroup$ Seems you gave almost the same answer before; maybe you want to consolidate the two versions over there? $\endgroup$ – Raphael Jun 5 '15 at 5:42

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