UIREADY.dev
Fast PowerLoading saved progress…

Fast Power

Exponentiation by squaring raises a base to an integer power in about log2(exp) multiplications instead of the exp multiplications you get from multiplying the base by itself over and over. The trick is that squaring the base lets you halve the exponent, so 2^30 takes roughly 5 steps rather than 30. You will implement fastPower(base, exp) where exp is any integer — positive, zero, or negative. See exponentiation by squaring for background; the built-in equivalent is Math.pow, which you may not call here.

Signature

fastPower(base, exp)
// base: number      (any real number)
// exp:  integer      (may be negative, zero, or positive)
// returns: number    (base raised to exp)

Examples

fastPower(2, 10);   // 1024
fastPower(10, 3);   // 1000
fastPower(5, 0);    // 1
fastPower(2, 30);   // 1073741824
fastPower(2, -1);   // 0.5   (1 / 2)
fastPower(2, -2);   // 0.25  (1 / 4)
fastPower(-2, 3);   // -8    (odd exponent keeps the sign)
fastPower(0, 5);    // 0

Notes

  • Logarithmic time — the point of this question is O(log exp) multiplications, not O(exp). A plain loop that multiplies exp times is correct but too slow for large exponents.
  • Integer exponent — exp is always a whole number, but it may be negative. base can be any number, including fractions and negatives.
  • Negative exponents — a negative exponent is a reciprocal: fastPower(b, -n) equals 1 / fastPower(b, n).
  • Exponent zero — any base to the power 0 is 1. This implementation also returns 1 for fastPower(0, 0), matching Math.pow.
  • No built-ins — implement the squaring yourself. Do not call Math.pow or use the ** operator.

FAQ

What is the time complexity of exponentiation by squaring?
It uses O(log exp) multiplications, because each pass squares the base and halves the exponent, so the number of steps is the number of binary digits in the exponent. The naive repeated-multiplication loop is O(exp) — for an exponent of a billion that is a billion multiplications versus about thirty.
How does it handle negative exponents?
A negative exponent is a reciprocal: fastPower(b, -n) returns 1 / fastPower(b, n). The one recursive call flips the exponent to positive, computes that power, and divides once, so the main squaring loop only ever deals with a non-negative exponent.
Why does the code check whether the exponent is odd?
The binary digits of the exponent decide which successive squares (base^1, base^2, base^4, and so on) get multiplied into the answer. A set low bit means the exponent is odd, which means the current square belongs in the product; you multiply it in, then halve the exponent to move on to the next bit.
Loading editor…