Solution

We are computing a base raised to an integer power with exponentiation by squaring — the same answer as multiplying it out, reached in a fraction of the steps.

The problem, in plain English

You want base raised to exp, where exp is a whole number that can be negative. The obvious approach multiplies base by itself exp times. That is fine for 2^10, but 2^1000000 would run a million multiplications, and it has no answer at all for a negative exponent. Exponentiation by squaring reaches the same result in a handful of steps by squaring the base and halving the exponent.

The mental model

Two facts drive the whole method. First, a power with an even exponent can be rewritten by squaring the base and halving the exponent: base^exp equals (base * base)^(exp / 2). Second, an odd exponent is just an even one with a single extra base peeled off. So you keep squaring the base and halving the exponent, and whenever the exponent is odd you set the current base aside to multiply into the answer. After about log2(exp) rounds the exponent hits 0 and you are done.

A first attempt

If you only picture the definition — base multiplied by itself exp times — the first version is a single counting loop.

function fastPowerNaive(base, exp) {
  let result = 1;
  for (let i = 0; i < exp; i++) {
    result *= base; // multiply by base, exp times
  }
  return result;
}

This returns the right number for small positive exponents, but it does exp multiplications — a billion of them when exp is a billion, even though log2 of a billion is only about 30. Worse, the loop body never runs when exp is negative, so fastPowerNaive(2, -2) silently returns 1 instead of 0.25. The real solution fixes both: handle the negative case up front, then replace the linear loop with squaring.

The working solution

function fastPower(base, exp) {
  // A negative exponent is a reciprocal: base to the -n is 1 / (base to the n).
  // Flip the sign once, solve the positive power, then divide.
  if (exp < 0) return 1 / fastPower(base, -exp);

  let result = 1;
  // Loop invariant: the final answer always equals result * base^exp.
  // Each pass keeps that true while pushing exp toward 0.
  while (exp > 0) {
    // If exp is odd, the current base is one of the squares that belongs
    // in the product (its binary bit is set), so fold it into result now.
    if (exp % 2 === 1) {
      result *= base;
    }
    base *= base;              // square the base: base^k becomes base^(2k)
    exp = Math.floor(exp / 2); // halve the exponent, dropping the handled bit
  }
  return result;
}

module.exports = { fastPower };

The negative guard runs at most once: it recurses with a positive exponent, so the loop below always sees exp at 0 or more. Inside the loop, result only grows on odd steps because the exponent's binary digits decide which squares to keep — more on that in the walkthrough. Squaring the base every pass is what makes the exponent shrink by half instead of by one, turning O(exp) work into O(log exp).

Walking through one call

Take fastPower(3, 13). The exponent is already positive, so skip the reciprocal guard and run the loop, reading the exponent from its low bit each pass:

• exp is 13 (odd): multiply result by the current base 3, so result is 3. Square the base to 9, halve exp to 6.
• exp is 6 (even): leave result at 3. Square the base to 81, halve exp to 3.
• exp is 3 (odd): multiply result by 81, so result is 243. Square the base to 6561, halve exp to 1.
• exp is 1 (odd): multiply result by 6561, so result is 1594323. Halve exp to 0.
• exp is 0: the loop stops and returns 1594323.

Why those three multiplications and not the even step? Because 13 in binary is 1101, which is 8 + 4 + 1. The base you carry grows through the successive squares 3, 3^2, 3^4, 3^8. A 1 bit means the matching square is part of the answer; the single 0 bit — the twos place — is the even step that skipped. So 3^13 is 3^8 * 3^4 * 3^1, exactly the three factors the loop multiplied in.

Gotchas

• Forgetting the negative case — a bare squaring loop returns 1 for fastPower(2, -2), because while (exp > 0) never runs. Handle exp below 0 first by returning 1 / fastPower(base, -exp).
• Multiply before you square — read the low bit and multiply result by the current base, then square the base. Squaring first folds base^2 in one step too early and gives the wrong power.
• Halving must floor — write exp = Math.floor(exp / 2) (or exp >>> 1 for exponents under 2^31). A plain exp / 2 leaves a fraction, so the odd test misfires and the loop never cleanly reaches 0.
• Precision is the real ceiling, not the algorithm — fastPower(2, 60) overflows JavaScript's exact-integer range of 2^53, so the result is a rounded double. For exact huge powers, hold base and result as BigInt.

Going further

• A recursive phrasing — the same idea reads cleanly as recursion: for an even exp, return fastPower(base * base, exp / 2); for an odd exp, return base * fastPower(base * base, (exp - 1) / 2). Same O(log exp) multiplications, but it uses O(log exp) call-stack frames instead of the loop's constant space.
• Modular exponentiation — cryptography needs base^exp mod m for enormous exponents. Take the remainder mod m after every multiply and every square so the numbers never blow up; this is the heart of RSA and Diffie–Hellman key exchange.
• Matrix exponentiation — the squaring trick works on matrices too. Raising a 2 by 2 matrix to the n-th power with this method computes the n-th Fibonacci number in O(log n) instead of O(n).