Make delicious recipes!

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:

  1. 'b' can be expressed as 2l + 2m + 2n ...

    Example:
    a10 = a8+2
    = a8 * a2


  2. Also note that multiplying a number by itself doubles the power.
    Example: a*a = a2
    and a4 * a4 = a8

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.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


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:

Site Owner: Sachin Goyal