Square and halve
Compute a huge power's remainder quickly by squaring. About 10 minutes.
Remainders can be taken early
Think of a car odometer that rolls over: only the last digits matter. Taking a remainder works the same way. Multiply two numbers and then reduce, or reduce each first and then multiply, and the answer is identical.
So reduce after every single multiplication, and the numbers never get large.
(7 * 8) % 5 # 1 ((7 % 5) * (8 % 5)) % 5 # 1
Start: result = 1. Instead of multiplying by 2 ten times, we'll square.
Halve the exponent
Computing 2 to the power 10 by multiplying ten times is slow. But it equals 4 to the power 5: square the base and halve the exponent. When the exponent is odd, first move one copy of the base into the result.
Each round halves the exponent, so even a million needs only about 20 rounds.
result = 1 % m
a %= m
while b > 0:
if b % 2 == 1:
result = result * a % m
a = a * a % m
b //= 2
return resultHow many squaring rounds does fast power need for b = 1,000,000?
- AAbout 20
- BAbout 1,000,000
- CAbout 1,000
Show the answer
About 20. 1,000,000 halves to 0 in about 20 steps, one round each.
Power with remainder
Return a^b % m. (a^0 is 1, and anything % 1 is 0.)
a = 2, b = 10, m = 1000 → 24
0 ≤ a ≤ 10^9 · 0 ≤ b ≤ 10^18 · 1 ≤ m ≤ 2 × 10^9