why 'code01' is more efficient than 'code02'? it seems like both codes are still getting the remainder after all the operation finished.
// code01
function power(base, exponent) {
if (exponent === 0) return 1;
const half = parseInt(exponent / 2);
const temp = power(base, half);
const result = (temp * temp) % 94906249;
if (exponent % 2 === 1) return (base * result) % 94906249;
else return result;
}
//code02
function power(base, exponent) {
if (exponent === 0) return 1;
return base * power(base, exponent - 1) % 94906249;
}
The first one uses exponent / 2 in the recursion, the second one exponent - 1.
Repeated division gives you logarithmic runtime, repeated subtraction gives you linear runtime.
Compare:
| division | subtraction |
|---|---|
| 8 | 8 |
| 4 | 7 |
| 2 | 6 |
| 1 | 5 |
| . | 4 |
| 3 | |
| 2 | |
| 1 | |
| . |
Division with a factor of 2 means 4 steps for input 8, 5 steps for input 16, 11 steps for input ~1000. Subtraction of 1 means 1000 steps for input 1000. 11 is a lot less than 1000.