MathMathematical Algorithms

Fast Exponentiation (Binary)

Compute x^n in O(log n) multiplications by squaring x and multiplying it in wherever the binary expansion of n has a 1 bit.

Learn Fast Exponentiation →

base | exponent — base up to 1000, exponent up to 10000 — e.g. "3 | 13"

e	e (binary)	e & 1	base	result
13	1101	·	3	1

1/13Compute 3^13 mod 1000000007. Write the exponent in binary (1101): each 1-bit contributes base^(2^k), so we square the base once per bit instead of multiplying 13 times.

Current iterationBit is 1: multiply result by baseBit is 0: skip the multiplyFinished

PseudocodeLearn Fast Exponentiation →

1result = 1; base = base mod M
2while e > 0:
3  if e & 1: result = result · base mod M   # this bit is set
4  base = base · base mod M
5  e = e >> 1
6return result

Variables

base3

e13

result1

M1000000007

Complexity

best O(log n)

avg O(log n)

worst O(log n)

space O(1)

Speed