Problems › JavaScript › patterns
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
Where you start
function powerMod(factor, exponent, 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 JavaScript
function powerMod(factor, exponent, divisor) {
let result = 1n;
let b = BigInt(factor) % BigInt(divisor);
let e = BigInt(exponent);
const m = BigInt(divisor);
while (e > 0n) {
if (e % 2n === 1n) result = (result * b) % m;
b = (b * b) % m;
e /= 2n;
}
return Number(result % m);
}