Fastest raise to power.

This tip submitted by Ezzetabi on 2005-03-18 16:31:04. It has been viewed 52013 times.
Rating of 5.6 with 209 votes

If you need raising to power some non standard object, like matrices or something overloaded with a integer exponent you can use this algorith:

a any type that know operator*, b int
      (a*a)^(b/2)         if b is even
a^b = 
      a*(a*a)*(int)^(b/2) if b is odd
using a recursive function your calculation will be faster (overall with big exponents) than the usual way.

A little example code:
double mpow (double, int);
double mpow2(double, int);

double mpow(double b, int exp)
   if (exp < 0)
      b = 1/b;
      exp *= -1;
   return mpow2(b,exp);

double mpow2(double b, int exp)
   if (exp > 2)
      if (exp%2)
         return b*mpow(b*b,(int)exp/2);
         return mpow(b*b,exp/2);
   else if (2 == exp)
      return b*b;
   else if (1 == exp)
      return b;

   return 1.0; // exp == 0
This example is about floats, so it is nothing more than the usual pow(), yet if you need raising to power try to avoid a*a*a*a*...*a as that is really slow.

More tips

Help your fellow programmers! Add a tip!