Faangprep Logo
Log inStart free
Browse curriculum

Fast Exponentiation

Fast exponentiation (binary exponentiation) computes (a^b) % m in O(log b) time.

3^13 MOD 1000 · 1101

BINARY

1

8

1

4

0

2

1

1

RESULT

1

BASE

3

Result

1

Base

3

Exponent left

13

Powers multiplied in

 

13 in binary is 1101. Each 1 is a power of 3 that has to be multiplied in; each 0 is one that is skipped.

Next

Bit 0 is 1, so fold in 3^1: 1 × 3 mod 1000 = 3.

Base

3

Exponent

13

Intuition

Calculating a^b by multiplying a, b times takes O(b) time. We can do better by squaring the base repeatedly. For example, a^8 = ((a^2)^2)^2. This takes only O(log b) steps.

Concept

  • Binary Representation: Any number b can be written as a sum of powers of 2 (e.g., 13 = 8 + 4 + 1).
  • Decomposition: a^13 = a^(8+4+1) = a^8 * a^4 * a^1.
  • Algorithm: Iterate through bits of b. If the current bit is 1, multiply the result by the current power of a. In every step, square a to get the next power.

How it Works

Steps:

  1. Initialize res = 1.
  2. While b > 0:
    • If b is odd (last bit is 1), res = res * a.
    • a = a * a (Square the base).
    • b = b / 2 (Shift right to process next bit).

Step-by-Step Breakdown

Watch the visualization:

  • Solid blue bit: The exponent bit being read. The row is written highest bit first, and the algorithm reads it from the lowest bit up.
  • Green bits: 1 bits whose power of the base has been multiplied into the result.
  • Grey, struck-through bits: 0 bits already read; they contribute nothing.
  • Result and Base: The result changes only on a 1 bit, and the base is squared after every bit.

When to Use

  • Calculating large powers modulo M (Cryptography).
  • Matrix Exponentiation (solving recurrences like Fibonacci in O(log N)).

When NOT to Use

  • Small exponents where simple loop is sufficient.
  • When precision is required for non-integer exponents.

How to Identify

"Calculate (A^B) % M", "N-th Fibonacci number for very large N".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Modular Arithmetic

Next

Bit Manipulation

Frequently Asked Questions

Why is it O(log b)?

The exponent is halved every iteration, so the loop runs about log2(b) times. Repeated multiplication would take b steps, so for b = 10^18 that is the difference between about 60 operations and 10^18.

Where does the binary representation come in?

Squaring the base each step produces a^1, a^2, a^4, a^8 and so on, and you multiply into the result exactly at the positions where b has a 1 bit. That rebuilds a^b from a sum of powers of two.

Why take the modulus at every step?

Because a^b overflows almost immediately. Multiplication distributes over the modulus, so reducing after each multiply keeps the running value below m and yields the same answer.