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
C# 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
public int PowerMod(int factor, int exponent, int divisor) {
}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 C#
public int PowerMod(int factor, int exponent, int divisor) {
long result = 1, b = factor % divisor, e = exponent, m = divisor;
while (e > 0) {
if (e % 2 == 1) result = (result * b) % m;
b = (b * b) % m;
e /= 2;
}
return (int) (result % m);
}