Raise to a power without the long way round
A hashing routine raises a factor to a large power and reports it modulo a divisor, so the number never gets out of hand.
- The exponent is zero or more.
- Report the result modulo the divisor, which is always at least 1.
- Anything raised to the power of zero is 1, then reduced modulo the divisor.
- Multiplying one at a time is too slow; the exponent can be very large.
power_mod(factor: int, exponent: int, divisor: int) → int
Where you start
def power_mod(factor: int, exponent: int, divisor: int) -> int:
Worked examples
| Call | Result |
|---|---|
power_mod(2, 10, 1000) | 24 |
power_mod(3, 0, 7) | 1 |
power_mod(5, 3, 1000) | 125 |
power_mod(2, 30, 1000000007) | 73741817 |
Hint
Squaring halves the exponent: x to the 2k is (x to the k) squared. Handle an odd exponent by peeling off one factor first.
Reference solution in Python
def power_mod(factor: int, exponent: int, divisor: int) -> int:
result = 1
b = factor % divisor
e = exponent
while e > 0:
if e % 2 == 1:
result = (result * b) % divisor
b = (b * b) % divisor
e //= 2
return result % divisor