Efficient implementation of Power(x,y)Easiest solution is: int power (a, b) { int result = 1; while (b--) result = result * a; return result; } But this requires the loop to run 'b' times. This can be improved to run only log(b) times as follows:
Using the above two properties, an efficient power function can be written as follows: int power (int a, int b) { int result = 1; while (b != 0) { if ((b&1) != 0) result *= a; b = b>>1; a = a*a; // Imp: self multiplication doubles the power of 'a' } return result; } Sample Run: power (1, 3) = 1 power (3, 4) = 81 power (2, 5) = 32 power (5, 5) = 3125 power (7, 3) = 343 power (10, 4) = 10000 The above binary breakup of power can be extended to multiplication too. Say you want to multiply x and y Break y into its binary equivalent. Run the same code as above, except change multiplication to addition and initialise the result to zero. |
Got a thought to share or found a
bug in the code?
We'd love to hear from you:
Name: | |
Email: | (Your email is not shared with anybody) |
Comment: |
Facebook comments: