No. 3 - Calculate Power in minimum multiplication

Problem:

Calculate x to the power y in minimum multiplications.

Solution 1:

The worse solution of this problem would be, have result=1 and run a loop y times and do result*=x y time. In this way complexity is O(n). So if y is 4 then it will do x*x*x*x, four multiplications.

A better solution would be to do result=x*x and then result=result*result, in this way there is only 2 multiplicaations. So for power of 2s we can clearly see the number of multiplication is log(n) time. What happens for other numbers like when y=7. We can divide seven in 4+2+1. so x^(4+2+1)=(x^4) * (x^2) * (x^1).
So we can see that all powers are now divided into power of some numbers which are powers of 2. For example x^y where y is 13, we can do 8+4+1. Clearly we can see when y is represented in binary, the set bits are indicative of how to calculate the result. So whenever the bit is set multiply the powers to the result. and then do power=power*power for the next bit.

CalculatePower.java

package com.meritmix.blog.algo;
/**
 * @author Ravi Yadav
 * This is copyright content of MeritMix.com
 * blog address is blog.meritmix.com 
 */
public class CalculatePower{
 public static void main(String[] args) {
  int x = 4;
  int y = 10;
  long answer = power(x, y);
  System.out.println(answer);
 }

 /**
  * @param x
  * @param y
  * @return
  */
 private static long power(int x, int y) {
  long power = x;
  long answer = 1;
  while (y != 0) {
   if ((y & 1) == 1) {
    answer *= power;
   }
   y >>= 1;
   power *= power;
  }
  return answer;
 }
}

Solution 2:

In case you don't like bitwise operation then same code is given below without bitwise operation.

CalculatePower2.java

package com.meritmix.blog.algo;

/**
 * @author Ravi Yadav
 * This is copyright content of MeritMix.com
 * blog address is blog.meritmix.com 
 */
public class CalculatePower2 {
 public static void main(String[] args) {
  int x = 4;
  int y = 10;
  long answer = power(x, y);
  System.out.println(answer);
 }

 /**
  * @param x
  * @param y
  * @return
  */
 private static long power(int x, int y) {
  long power = x;
  long answer = 1;
  while (y != 0) {
   if ((y % 2) == 1) {
    answer *= power;
   }
   y /= 2;
   power *= power;
  }
  return answer;
 }
}

Solution 3:

Lets analyze the problem again. any power of x can be represented in a recursive way like x² as x¹*x¹ and x⁴ as (x²)² and x⁶ as (x²)³ or (x²)*(x²)². So lets convert this into code now.

CalculatePowerRecursive.java

package com.meritmix.blog.algo;
/**
 * @author Ravi Yadav
 * This is copyright content of MeritMix.com
 * blog address is blog.meritmix.com 
 */
public class CalculatePowerRecursive {
 public static void main(String[] args) {
  int x = 4;
  int y = 10;
  long answer = power(x, y);
  System.out.println(answer);
 }

 /**
  * @param x
  * @param y
  * @return
  */
 private static long power(int x, int y) {

  if(y==1){
   return x;
  }
  if(y%2==0){
   return power(x*x, y/2);
  }else{
   return x*power(x*x, y/2);
  }
 }
}

Back to Menu

Section