Fast Power Algorithm
FAST!
time complexity $\Omicron(pow)$
Implementation
Recursive
| int power(int base, int pow) {
if (!pow)
return 1;
if (n & 1) // if n is odd
return base * power(base, (pow - 1) >> 1) * power(base, (pow -1) >> 1);
return power(base, pow >> 1) * power(base, pow >> 1);
}
|
Iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | int power(int base, int pow) {
if (!pow)
return 1;
int result = 1;
while (pow) {
if (pow & 1) {
result *= base;
pow--; // not necessary
}
pow >>= 1;
base *= base;
}
return result;
}
|
How it works?
