World's most popular travel blog for travel bloggers.

[Answers] Computational complexity of function $U^V$

, , No Comments
Problem Detail: 

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?

Asked By : seek

Answered By : Rick Decker

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$.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43228

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback