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.
powerMod(factor: int, exponent: int, divisor: int) → int
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func powerMod(factor int, exponent int, divisor int) int {
}Worked examples
| Call | Result |
|---|---|
powerMod(2, 10, 1000) | 24 |
powerMod(3, 0, 7) | 1 |
powerMod(5, 3, 1000) | 125 |
powerMod(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 Go
func powerMod(factor int, exponent int, divisor int) int {
result, b, e, m := int64(1), int64(factor%divisor), int64(exponent), int64(divisor)
for e > 0 {
if e%2 == 1 {
result = (result * b) % m
}
b = (b * b) % m
e /= 2
}
return int(result % m)
}