FastPowering

README

Fast Powering Algorithm

The power of a number says how many times to use the number in a multiplication.

Naive Algorithm Complexity

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

We can get better execution time by using a divide and conquer approach to compute power which can before up to O(log(n)).

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

For example

2^4 = (2 * 2) * (2 * 2) = (2^2) * (2^2)

2^5 = (2 * 2) * (2 * 2) * 2 = (2^2) * (2^2) * (2)

Time Complexity

O(log(n))

Implementation

• Fast powering

References

• Wikipedia
• GeeksForGeeks
• StackExchange