N-th power of complex number z = x + iy in O(log n) time

Question

You are given a complex number z = x + iy.  The n-th power of z is given (x + iy)^n.  Describe a O(log n) time algorithm to do the same.  Recall that that i^2 = -1, and that z^2 = x^2 – y^2 + 2ixy. 

Answer 1

We can use Divide and Conquer to solve this problem, with the basic concept being that of repeated squaring. We use the standard mathematical model where multiplications take O(1) time. 

For example, we can calculate z^16 from z^8 in constant time. We just adjust this idea to take into account that number n may be odd or even as follows: 

  power (int z, int n) {

 If (n == 1)

          return z

   mid = n/2 // Integer division, return floor value.

   int previous = power (a, mid); //recursive call

If n%2 == 1

           return previous *previous *z

else

  return previous * previous

}

  We observe that the recurrence relation becomes : T(n) = T(n/2) + 1 which will lead to O(logn) time. 

Answer 2

This can be implemented using Divide and Conquer.

Where if n is negative, return 1/(x+iy)^-n

if n is 1 return x+iy

if n is 0 return 1

For the other scenarios:

 if n is greater than 1 return (x+iy)^(n/2) * (x+iy)^(n/2)

and if n is odd return want to do the above but multiply an additional (x+iy) - translating to:  (x+iy)^(n/2) * (x+iy)^(n/2) * (x+iy)

With this the recurrence relation would result in T(n) = T(n/2) + O(1)

providing with a time complexity of O(log n).

Comments

Instead of the code/psuedocode, is it possible to provide the algorithm, the recurrence relation, and the time complexity analysis?

Answer 3

In this question, we can use Divide and Conquer to solve this problem.

power(int z, int n) {

    if(n == 1)

        return z

        int  p= power (z, n/2);

    if(n % 2 == 0)

        return cmul (p,p)

    if(n % 2 != 0)

        return cmul(z, cmul(p, p));

}

So, we can find that the recurrence relation is T(n) = T(n/2) + 1 

Hence, the time complexity is O(logn) time. 

Answer 4

The Divide and Conquer approach can be used to solve this problem, specifically due to the repeated squaring of numbers. Standard mathematical operations take O(1) (constant) time.

 

Algorithm:

exponent(i, j)

            If j == 1

                        Return i

middle = j/2

prior = exponent(x, middle)

 

if j % 2 == 1

            previous * previous * i

 

else

            previous * previous

 

Recurrence Relation:

T(n) = T(n/2) + 1

 

This recurrence relation leads to O(log n) time

Answer 5

The expression (x + iy)^n can also be expressed as (x + iy)^n/2 *  (x + iy)^n/2. We can observe that we can split the problem in half into two identical subproblems. This suggests that divide and conquer can be used to accelerate the calculation.

Each time we divide the problem we can see that the exponent halves. The problem only needs to be divided down to n = 1, which would be the base case. The number of divisions required to breakdown the problem to the base case would increase by one for every time n doubled. This can be recognised as logarithmic growth.

Earlier we identified that each division would contain duplicate subproblems. In order to conquer each division we can multiply the one of the subsolutions by itself rather than recursing and recalculating the subproblem. This eliminates the need to recurse a second time.

The recurrence relation is as follows:

T(n) = T(n/2) + 1
We can solve the recurrence relation to be T(n) = O(log(n))

Therefore, by using divide and conquer the problem of solving (x+iy)^n can be solved efficiently in log(n) time.

Answer 6

We can use divide and conquer for this problem, only because the we observe the squaring in this case to the power of 2 repeated. We also observe a constant c in this problem, which empowers us to us the standard mathematical model big O(1) as a multiplier. Thus the pseudocode for this problem:
 

power(int z, int n) {
   if (n ==1)

        return z

//division of integer, return the largest integer value that is smaller than or equal to the number (z)

mid = int n/2

int previous = power (a,mid); // this recursive call else if

if n%2 == 1

return prev * prev * z

else

return prev*prev

//end

}

Recurrence Relation: T(n) = T(n/2) + 1

Time Complexity: O(log n ) time