Calculating the power of a number $x^n$ is a fundamental operation. While the most straightforward approach involves iterative multiplication, more efficient techniques exist to handle large exponents or performance-critical applications.

The Linear Time Approach

The most intuitive method to compute $x^n$ is to multiply the base $x$ by itself $n$ times. This is often implemented using a simple loop:

function powerLinear(base, exponent) {
  let total = 1;
  for (let i = 0; i < exponent; i++) {
    total *= base;
  }
  return total;
}

This approach has a time complexity of $O(n)$, which becomes inefficient as the exponent grows.

Binary Exponentiation Logic

Fast exponentiation, also known as binary exponentiation, reduces the complexity to $O(\log n)$. It leverages the binary representation of the exponent. For instance, to calculate $x^{13}$, we can represant 13 in binary as $1101_2$, which means:

$13 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 8 + 4 + 1$

Thus:

$x^{13} = x^8 \cdot x^4 \cdot x^1$

Instead of 13 multiplications, we only need to square the base repeatedly and multiply the result when the corrresponding bit in the exponent is set.

function fastPower(base, exp) {
  let result = 1;
  let currentBase = base;
  let remainingExp = exp;

  while (remainingExp > 0) {
    // Check if the lowest bit is 1
    if ((remainingExp & 1) === 1) {
      result *= currentBase;
    }
    // Square the base for the next bit position
    currentBase *= currentBase;
    // Unsigned right shift to process the next bit
    remainingExp >>>= 1;
  }
  return result;
}

Handling Negative Exponents

When dealing with negative exponents, the mathematical identity $x^{-n} = (1/x)^n$ is used. We can adapt the algorithm to handle this by transforming the base or the final result.

function computePower(x, n) {
  if (n === 0) return 1;
  
  let p = n < 0 ? -n : n;
  let val = n < 0 ? 1 / x : x;
  let accumulation = 1;

  while (p > 0) {
    if (p % 2 === 1) {
      accumulation *= val;
    }
    val *= val;
    p = Math.floor(p / 2);
  }

  return accumulation;
}

Modular Arithmetic for Large Numbers

In some scenarios, such as finding the last digit of a very large power (where $a$ and $b$ are passed as strings), we can use modular exponentiation. Since we only care about the last digit, we can apply the modulo operator % 10 at each step to prevent numerical overflow and maintain precision.

function getLastDigit(baseStr, expStr) {
  let baseDigit = parseInt(baseStr[baseStr.length - 1]);
  let exponent = parseInt(expStr);
  
  if (baseDigit === 0) return 0;
  
  let res = 1;
  while (exponent > 0) {
    if (exponent & 1) {
      res = (res * baseDigit) % 10;
    }
    baseDigit = (baseDigit * baseDigit) % 10;
    exponent >>>= 1;
  }
  
  return res;
}

console.log(getLastDigit("1234567", "4")); // Output: 1 (7^4 = 2401)

Optimization in String Operations

The principles of binary exponentiation are not limited to arithmetic. They can be applied to string manipulation, such as repeating a string $n$ times. Instead of $O(n)$ concatenations, we use the same logarithmic strategy.

function repeatStringEfficiently(text, count) {
  let result = "";
  let pattern = text;
  let remainingCount = count;

  while (remainingCount > 0) {
    if (remainingCount & 1) {
      result += pattern;
    }
    pattern += pattern;
    remainingCount >>>= 1;
  }

  return result;
}

console.log(repeatStringEfficiently("abc", 3)); // "abcabcabc"