javascript-algorithms
Fast Powering Algorithm
Read this in other languages: français.
The power of a number says how many times to use the number in a multiplication.
It is written as a small number to the right and above the base number.
Naive Algorithm Complexity
How to find a raised to the power b?
We multiply a to itself, b times. That
is, a^b = a * a * a * ... * a (b occurrences of a).
This operation will take O(n) time since we need to do multiplication operation
exactly n times.
Fast Power Algorithm
Can we do better than naive algorithm does? Yes we may solve the task of
powering in O(log(n)) time.
The algorithm uses divide and conquer approach to compute power. Currently the
algorithm work for two positive integers X and Y.
The idea behind the algorithm is based on the fact that:
For even Y:
X^Y = X^(Y/2) * X^(Y/2)
For odd Y:
X^Y = X^(Y//2) * X^(Y//2) * X
where Y//2 is result of division of Y by 2 without reminder.
For example
2^4 = (2 * 2) * (2 * 2) = (2^2) * (2^2)
2^5 = (2 * 2) * (2 * 2) * 2 = (2^2) * (2^2) * (2)
Now, since on each step we need to compute the same X^(Y/2) power twice we may optimise
it by saving it to some intermediate variable to avoid its duplicate calculation.
Time Complexity
Since each iteration we split the power by half then we will call function
recursively log(n) times. This the time complexity of the algorithm is reduced to:
O(log(n))