cf.completefrontend
MATH & GEOMETRY · CORE

Fast exponentiation

Compute base to the power exponent in about log exponent multiplications by squaring the base and using the exponent's binary digits.

Time O(log n)Space O(1)5 practice problemsStep-through picture

The idea

Computing 3^13 the slow way takes 12 multiplications: 3 × 3 × 3 × .... For an exponent of a billion, that's a billion multiplications.

Fast exponentiation, also called exponentiation by squaring, uses the binary digits of the exponent. 13 in binary is 1101, which means 13 = 8 + 4 + 1, so 3^13 = 3^8 × 3^4 × 3^1. You can get 3^1, 3^2, 3^4, 3^8 by squaring again and again: each square doubles the power. Then multiply together the ones whose binary digit is 1.

The loop reads the exponent's binary digits from the right: if the lowest digit is 1, multiply the result by the current square. Then square the square and drop the lowest digit. An exponent of a billion has only 30 binary digits, so it takes about 30 steps.

An everyday example

Paying with coins that double in value

Imagine coins worth 1, 2, 4, 8, 16, and so on, each worth double the last. To pay 13, you don't hand over thirteen 1-coins. You pay with an 8, a 4, and a 1. To decide which coins to use, look at 13 in binary: 1101 says use the 8, the 4, and the 1, but not the 2. Fast exponentiation does the same with powers: it builds 3^13 from 3^8, 3^4, and 3^1.

How the example maps to the code
In the exampleIn the code
The next coin, worth double the lastsquare *= square
Whether to use this coine % 2 === 1
Adding the coin to the paymentresult *= square
Moving on to the next coin sizee = Math.floor(e / 2)

From the slow way to fast exponentiation

  1. Start with the obvious way: multiply base by itself again and again. 3^21 takes 20 multiplications, and an exponent of a billion takes a billion. The work grows with the size of the exponent, even though the exponent itself is only a few digits long.
  2. Notice what squaring does. 3^2 × 3^2 is 3^4, and 3^4 × 3^4 is 3^8: each square doubles the exponent. From 3 you reach 3^16 in only 4 squarings. So powers whose exponent is a power of two are cheap.
  3. Every exponent is a sum of powers of two: those are its binary digits. 21 is 10101 in binary, which means 16 + 4 + 1. So 3^21 = 3^16 × 3^4 × 3^1, and each of those factors is one of the cheap squares. We only need to multiply together the squares whose binary digit is 1.
  4. Read the binary digits from the right while squaring at the same pace. e % 2 is the lowest digit; if it's 1, multiply the current square into result. Then square square and drop the digit with e = Math.floor(e / 2). Stop when e is 0. That loop is fast exponentiation.

How it works

  1. Set result = 1, square = base, and e = exponent.
  2. While e > 0, look at the lowest binary digit of e: e % 2.
  3. If it is 1, multiply result by square.
  4. Square square, so it moves from base^1 to base^2 to base^4 and so on.
  5. Drop the lowest binary digit: e = Math.floor(e / 2).
  6. When e is 0, result holds base^exponent.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function power(base, exponent) {
  2. let result = 1;
  3. let square = base;
  4. let e = exponent;
  5. while (e > 0) {
  6. if (e % 2 === 1) {
  7. result *= square;
  8. }
  9. square *= square;
  10. e = Math.floor(e / 2);
  11. }
  12. return result;
  13. }

How fast it is

TimeO(log n)
Extra memoryO(1)

The exponent n has about log₂ n binary digits, and each loop step handles one. Only three numbers are stored.

  • Best caseO(1)

    exponent is 0 or 1. The loop runs zero times or once.

  • Average caseO(log n)

    One loop step per binary digit of the exponent n. About half the digits are 1, so about 1.5 multiplications per step.

  • Worst caseO(log n)

    An exponent whose binary digits are all 1, like 1023 (1111111111). Every step multiplies twice: 10 steps and 20 multiplications.

Common mistakes

  • Using plain numbers for modular powers with a modulus near 10^9. The product passes 2^53 and the last digits come out wrong. Use BigInt for the multiplication.
  • Forgetting a negative exponent. base^-n is 1 / base^n, so handle the sign first and use the positive exponent in the loop.
  • Writing e = e / 2 without Math.floor. e becomes a fraction and the loop never sees a clean 0.
  • Using e & 1 and e >> 1 with exponents above 2^31. Bit operators work on 32-bit integers in JavaScript, so large exponents are cut off. Use % 2 and Math.floor(e / 2) or BigInt.

When to use it

Look for these clues in a problem:

  • The problem raises something to a huge power, such as 10^9 or 10^18.
  • The answer must be given "modulo 1000000007" after a large power.
  • Something is applied the same way n times, with n huge (combine with matrix exponentiation).
  • You need a modular inverse with a prime modulus (Fermat's rule: a^(p-2) mod p).

Check yourself

Answer each one in your head first, then open it.

How many loop steps does power(x, 1000) take?

10, because 1000 is 1111101000 in binary, which has 10 digits. Each step handles one digit.

Why can the very last squaring cause trouble even when the answer is small enough?

It squares square once more after the last digit is used. That value is never needed but can be the largest in the loop, so it can overflow or lose precision. Some versions skip the square when e is 1.

What does power(2, -3) return, and why?

1, because e > 0 is false at once and the loop never runs. Negative exponents must be handled before the loop.

Why is it fine that Math.floor(e / 2) throws away the lowest digit?

That digit was just used: if it was 1, square was already multiplied into result. Dropping it moves the next digit into the lowest place for the next step.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one promise at the top of every step: result × square^e equals base^exponent. At the start it reads 1 × base^exponent, so it's true. In the trace, at the row where e = 5, result is 3 and square is 81, and 3 × 81^5 = 3 × 3^20 = 3^21.

Each step keeps the promise. If e is odd, moving one square into result turns square^e into square^(e - 1), and e - 1 is even. Squaring square and halving e leaves square^e unchanged, because (s²)^(e/2) = s^e. Math.floor(e / 2) is the same as (e - 1) / 2 for an odd e, so both cases fit.

The loop ends because e at least halves on every step, so it reaches 0 after as many steps as exponent has binary digits: 5 for 21, 30 for a billion. At that point the promise reads result × square^0 = result, so result equals base^exponent.

Going deeper

3 more ideas

Why it gives the right power

At every step, result × square^e equals the original base^exponent. At the start that's 1 × base^exponent. If e is odd, moving one square into result turns square^e into square^(e-1). Then square^(e-1) with e - 1 even equals (square²)^((e-1)/2), which is exactly what squaring square and halving e does. When e is 0, the rule says result is the answer.

The modular version, and JavaScript numbers

Large powers are usually wanted modulo some m, such as 1000000007. Apply % m after every multiplication: result = (result * square) % m and square = (square * square) % m. But in JavaScript, two numbers near 10^9 multiply to about 10^18, past 2^53, where numbers lose precision. Use BigInt for those products, as in (result * square) % m with 1n-style values, then convert back with Number(...).

The cost

The loop runs once per binary digit of the exponent, so O(log exponent) steps. Each step does at most two multiplications. Computing x^(10^18) takes about 60 steps.

Work it by hand

Every step in a table, with why

Compute 3^21. Its binary digits 10101 alternate, so the trace shows both kinds of step.

base = 3, exponent = 21

Stepee % 2resultsquare afterWhat happensWhy
121-13startresult starts at 1, which is 3^0. square holds 3^1.
221139multiply, then squareThe lowest digit of 21 is 1, so 3^1 is part of the answer: result = 3. square becomes 3^2 = 9, and e becomes 10.
3100381only squareThe lowest digit of 10 is 0, so 3^2 is not part of the answer. square becomes 3^4 = 81, and e becomes 5.
4512436561multiply, then squareDigit 1: result = 3 × 81 = 243, which is 3^5. square becomes 3^8 = 6561, and e becomes 2.
52024343046721only squareDigit 0: skip 3^8. square becomes 3^16 = 43046721, and e becomes 1.
611104603532031853020188851841multiply, then squareDigit 1: result = 243 × 43046721 = 10460353203, which is 3^21. The loop still squares once more, to 3^32, a value it never uses.
70-10460353203-e is 0: returnAll five binary digits are used up, so result is the answer.

It returns 10460353203, which is 3^21, after 5 loop steps and 8 multiplications instead of 20. The biggest number in the loop was the unused last square, 3^32.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Fast exponentiationO(log n)O(1)Whole exponents, exact or modular answers, and large exponents: the standard choice.
Repeated multiplicationO(n)O(1)Tiny exponents only, where the simpler loop is easier to read.
Recursive squaringO(log n)O(log n)When the recursive form makes a proof or a generic "power of anything" helper clearer.
Built-in ** or Math.powO(1)O(1)A floating-point answer is fine and there's no modulus. It can't reduce modulo m along the way.

Extra memory: O(1): three numbers, result, square, and e. A recursive version uses O(log n) space for its call stack.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Fast exponentiation and the other approaches, on a scale where each line up is 10 times more steps.
  • Fast exponentiation, Recursive squaring O(log n)
  • Repeated multiplication O(n)
  • Built-in ** or Math.pow O(1)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Fast exponentiation31020
Repeated multiplication101,0001 million
Recursive squaring31020
Built-in ** or Math.pow111

Inputs that need care

5 tricky inputs
exponent = 0
The loop never runs and it returns 1, even for power(0, 0). That matches JavaScript, where 0 ** 0 is also 1.
A negative exponent: power(2, -3)
e > 0 is false at once, so it returns 1, which is wrong. Handle the sign first: 1 / power(base, -exponent) gives 0.125.
A negative base: power(-2, 5)
It works without changes and returns -32, because the sign is just another factor that gets multiplied in an odd number of times.
A result past 2^53: power(7, 19)
It returns 11398895185373144, but the true value ends in ...143. Plain numbers lose the last digits. Use BigInt values like 7n, or work modulo a number.
A decimal exponent: power(4, 0.5)
e % 2 is 0.5, never 1, and e drops to 0 at once, so it returns 1 instead of 2. The loop only works for whole exponents; use ** or Math.sqrt for fractions.

Variations and follow-ups

Twists interviewers add

Modular power

When the answer is wanted modulo m, reduce after every multiplication: result = result * square % m and square = square * square % m, using BigInt so the products stay exact. This is how modular inverses are computed: b^(m - 2) % m when m is prime.

Recursive squaring

x^n is (x^(n/2))² when n is even and x × x^(n-1) when it's odd. It's the same idea read from the top binary digit down. It's easy to prove, but it uses a call stack of depth log n.

Powers of other things

The loop works for anything with an associative multiply. Raising a matrix to a power jumps a step-by-step rule forward n steps. Composing a shuffle with itself k times gives where each card ends up after k shuffles.

Left-to-right binary

Read the exponent's digits from the highest down: square result at each digit, and multiply by base when the digit is 1. It does the same number of steps, and every multiplication is by the original base, which can be cheaper when base is small.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from a huge exponent ("compute x^n where n is up to 10^18"), from "modulo 10^9 + 7" combined with a power, or from "apply this step k times" where k is huge.
  • Explain it with the binary digits: "21 is 16 + 4 + 1, so I multiply together x^16, x^4, and x^1, which I get by squaring." Then say the promise, result × square^e stays equal to the answer.
  • Test exponent = 0, exponent = 1, a negative exponent, and a power of two like 8, where only the last step multiplies into result.
  • The usual follow-up is "what about the modulus and overflow?". Answer: reduce after every multiplication and use BigInt, because two numbers near 10^9 multiply to about 10^18, past 2^53.

Where frontend code uses it

The same idea in real UI code
  • The Web Crypto API (crypto.subtle) supports RSA signatures and encryption, and RSA is built on modular exponentiation of very large numbers.
  • Exponential backoff for retrying failed requests waits base × 2^attempt milliseconds. That power is small, but it is the same idea of repeated doubling.
  • Teaching tools and code playgrounds that work with BigInt use fast exponentiation to compute huge powers, such as 2n ** 1000n style values, quickly.

Related algorithms