Power of Powers - Minimum Number of Multiplications to compute Nth Power

Task Description

You need to find the minimum number of multiplications needed to get the desired power $n$ of a number $x$ using only previous computations.

Examples

The minimum number of multiplications required to compute $16th$ power of a number $x$ is $4$.

1. $x \times x = x^2$
2. $x^2 \times x^2 = x^4$
3. $x^4 \times x^4 = x^8$
4. $x^8 \times x^8 = x^{16}$

Similarly, the minimum number of multiplications required to compute the $15th$ power of the number is $5$.

1. $x \times x = x^2$
2. $x^2 \times x^2 = x^4$
3. $x^4 \times x = x^5$
4. $x^5 \times x^5 = x^{10}$
5. $x^5 \times x^{10} = x^{15}$

OR

1. $x \times x = x^2$
2. $x^2 \times x = x^3$
3. $x^3 \times x^3 = x^6$
4. $x^6 \times x^6 = x^{12}$
5. $x^{12} \times x^3 = x^{15}$

Solution

As can be seem from the examples, the $nth$ power of a number can be computed using previous results for power $\lt n$.

Also, as seen from the examples, there can be different combination of previous result to compute the $nth$ power. For example, we can compute $x^{15}$ using $x^5 \times x^{10}$ or using $x^{12} \times x^3$. Obviously we have multiple choices to compute this value.

Minimum Number of Multiplications

Let, $x^n = x^a \times x^b \times x^c \times x^d$ be one of the combination
Then, number of multiplication needed using this combination

$=$ number of multiplication for $x^a$ + number of multiplication for $x^b$ + number of multiplication for $x^c$ + number of multiplication for $x^d$ + 3

The last number $3$ comes from the fact that we need $3$ more multiplications to multiply $x^a,\ x^b,\ x^c\ and\ x^d$.

The required minimum number of multiplications will be the minimum of all such combinations.

Computing the Number of Multiplications for all Combinations

int min = Integer.MAX_VALUE;
for i = 2 to n/2
   // x^15, 15/2 = 7, there are 2 x^7 and we need to multiply x^7 (2-1) times
   int part1 = (i-1) + numberOfMultiplicationFor(n / i);

   // 15 % 2 = 1, 
   int part2 = numberOfMultiplicationFor(n % i)
   
   int combinationNumber =  part1 + part2;

   // if n % i != 0, we need extra 1 multiplication x^14 x x
   combinationNumber += n % i == 0 ? 0 : 1;
   
   min = Math.min(min, combinationNumber)

Special Case for Even n

For Even n, we can simply compute the number of multiplication required using,

// this will be minimum for Even n
numberOfMultiplication = numberOfMultiplicationFor(n/2) + 1;

Recursive Implementation

    if f(n) gives the minimum number of multiplication required to compute
       nth power, then

    f(n) = f(n/2) + 1 if n is even
         = Min{
                for i = 2 to n/2 
                  (i-1) + f(n/i) + f(n%i) + (1 if n%i != 0)
              }

    Base Cases:
      f(0) = f(1) = 0
      f(2) = 1
      f(3) = 2
  

Recursive implementation will give the result, but if we don't use memoization, then it will end up calculating the same value again and again. This will result into high complexity.

To improve the complexity, we can either use Memoization or Botton Up Dynamic programming. Following the Dynamic Programming solution.

Bottom Up Dynamic Programming Approach

---

---

---