Skip to content

Files

Latest commit

bae925b · Apr 22, 2020

History

History

FastPowering

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Apr 22, 2020
Apr 21, 2020
Apr 21, 2020

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

References