Fast Powering Algorithm - DSA and Algorithm - JavaScript

 

The Fast Powering Algorithm algorithm is a very interesting question that you may have heard in your school or college asked in many interviews including FAANG companies.  

The power of a number says how many times to use the number in multiplication.

It is written as a small number to the right and above the base number.

How to find a raise to the power b?

We multiply a to itself, b times. That is, a^b = a * a * a * ... * a (b occurrences of a).

This operation will take O(n) time since we need to do multiplication operations exactly n times.

Can we do better than the naive algorithm does? Yes, we may solve the task of powering in O(log(n)) time.

The algorithm uses a divide-and-conquer approach to computing power. Currently the algorithm work for two positive integers X and Y.

The idea behind the algorithm is based on the fact that:

For even Y:

X^Y = X^(Y/2) * X^(Y/2)

For odd Y:

X^Y = X^(Y/2) * X^(Y/2) * X

where Y//2 is the result of the division of Y by 2 without remainder.

For example:

2⁴ = (2 * 2) * (2 * 2) = (2²) * (2²)

2⁵ = (2 * 2) * (2 * 2) * 2 = (2²) * (2²) * (2)

Now, since on each step we need to compute the same X^(Y/2) power twice we may optimize it by saving it to some intermediate variable to avoid its duplicate calculation.

Time Complexity

Since each iteration we split the power by half then we will call the function recursively log(n) times. This the time complexity of the algorithm is reduced to:

O(log(n))

Let's start with the algorithm,

 var  fastPowering = function(base,power) {

   if (power === 0) {

    // Anything that is raised to the power of zero is 1.

    return 1;

  }

  if (power % 2 === 0) {

    // If the power is even...

    // we may recursively redefine the result via twice smaller powers:

    // x⁸ = x⁴ * x⁴.

    const multiplier = fastPowering(base, power / 2);

    return multiplier * multiplier;

  }

  // If the power is odd...

  // we may recursively redefine the result via twice smaller powers:

  // x⁹ = x⁴ * x⁴ * x.

  const multiplier = fastPowering(base, Math.floor(power / 2));

  return multiplier * multiplier * base;

};

I hope you understood the algorithm. If you have any doubts, please let us know in the comments.