forked from mberktas/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
fastPowering.js
30 lines (28 loc) · 893 Bytes
/
fastPowering.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Fast Powering Algorithm.
* Recursive implementation to compute power.
*
* Complexity: log(n)
*
* @param {number} base - Number that will be raised to the power.
* @param {number} power - The power that number will be raised to.
* @return {number}
*/
export default function fastPowering(base, power) {
if (power === 0) {
// Anything that is raised to the power of zero is 1.
return 1;
}
if (power % 2 === 0) {
// If the power is even...
// we may recursively redefine the result via twice smaller powers:
// x^8 = x^4 * x^4.
const multiplier = fastPowering(base, power / 2);
return multiplier * multiplier;
}
// If the power is odd...
// we may recursively redefine the result via twice smaller powers:
// x^9 = x^4 * x^4 * x.
const multiplier = fastPowering(base, Math.floor(power / 2));
return multiplier * multiplier * base;
}