|
1 | 1 | #Fast Powering Algorithm |
2 | 2 |
|
3 | | -This computes power of (a,b) |
4 | | -eg: power(2,3) = 8 |
5 | | -power(10,0) = 1 |
| 3 | +**The power of a number** says how many times to use the number in a |
| 4 | +multiplication. |
6 | 5 |
|
7 | | -The algorithm uses divide and conquer approach to compute power. |
8 | | -Currently the algorithm work for two positive integers X and Y |
9 | | -Lets say there are two numbers X and Y. |
10 | | -At each step of the algorithm: |
11 | | -1. if Y is even |
12 | | - then power(X, Y/2) * power(X, Y/2) is computed |
13 | | -2. if Y is odd |
14 | | - then X * power(X, Y/2) * power(X, Y/2) is computed |
| 6 | +It is written as a small number to the right and above the base number. |
15 | 7 |
|
16 | | -At each step since power(X,Y/2) is called twice, this is optimised by saving the result of power(X, Y/2) in a variable (lets say res). |
17 | | -And then res is multiplied by self. |
| 8 | + |
18 | 9 |
|
19 | | -Illustration through example |
20 | | -power (2,5) |
21 | | -- 2 * power(2,2) * power(2,2) |
22 | | - power(2,2) |
23 | | -- power(2,1) * power(2,1) |
24 | | - power(2,1) |
25 | | -- return 2 |
| 10 | +##Naive Algorithm Complexity |
26 | 11 |
|
27 | | -Going up the tree once the end values are computed |
28 | | - power(2,1) = 2 |
29 | | - power(2,2) = power(2,1) * power(2,1) = 2 * 2 = 4 |
30 | | -power(2,5) = 2 * power(2,2) * power(2,2) = 2 * 4 * 4 = 32 |
| 12 | +How to find`a` raised to the power`b`? |
31 | 13 |
|
| 14 | +We multiply`a` to itself,`b` times. That |
| 15 | +is,`a^b = a * a * a * ... * a` (`b` occurrences of`a`). |
32 | 16 |
|
33 | | -Complexity relation: T(n) = T(n/2) + 1 |
| 17 | +This operation will take`O(n)` time since we need to do multiplication operation |
| 18 | +exactly`n` times. |
34 | 19 |
|
35 | | -Time complexity of the algorithm: O(logn) |
| 20 | +##Fast Power Algorithm |
36 | 21 |
|
37 | | -##References |
| 22 | +Can we do better than naive algorithm does? Yes we may solve the task of |
| 23 | + powering in`O(log(n))` time. |
| 24 | + |
| 25 | +The algorithm uses divide and conquer approach to compute power. Currently the |
| 26 | +algorithm work for two positive integers`X` and`Y`. |
| 27 | + |
| 28 | +The idea behind the algorithm is based on the fact that: |
| 29 | + |
| 30 | +For**even**`Y`: |
| 31 | + |
| 32 | +```text |
| 33 | +X^Y = X^(Y/2) * X^(Y/2) |
| 34 | +``` |
| 35 | + |
| 36 | +For**odd**`Y`: |
| 37 | + |
| 38 | +```text |
| 39 | +X^Y = X^(Y//2) * X^(Y//2) * X |
| 40 | +where Y//2 is result of division of Y by 2 without reminder. |
| 41 | +``` |
| 42 | + |
| 43 | +**For example** |
38 | 44 |
|
| 45 | +```text |
| 46 | +2^4 = (2 * 2) * (2 * 2) = (2^2) * (2^2) |
| 47 | +``` |
| 48 | + |
| 49 | +```text |
| 50 | +2^5 = (2 * 2) * (2 * 2) * 2 = (2^2) * (2^2) * (2) |
| 51 | +``` |
| 52 | + |
| 53 | +Now, since on each step we need to compute the same`X^(Y/2)` power twice we may optimise |
| 54 | +it by saving it to some intermediate variable to avoid its duplicate calculation. |
| 55 | + |
| 56 | +**Time Complexity** |
| 57 | + |
| 58 | +Since each iteration we split the power by half then we will call function |
| 59 | +recursively`log(n)` times. This the time complexity of the algorithm is reduced to: |
| 60 | + |
| 61 | +```text |
| 62 | +O(log(n)) |
| 63 | +``` |
| 64 | + |
| 65 | +##References |
39 | 66 |
|
| 67 | +-[YouTube](https://www.youtube.com/watch?v=LUWavfN9zEo&index=80&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&t=0s) |
| 68 | +-[Wikipedia](https://en.wikipedia.org/wiki/Exponentiation_by_squaring) |