pow() implementation in cmath and efficient replacement

Question

I've read that cmath calculates pow(a,b) by performing exp(b*log(a)). This should not be used when b is an integer, since it slows down calculations a lot. What alternatives are there when

1. calculating a lot of successive pow()s with the same constant a
2. it is known beforehand that b will definitely be an integer?

I am looking for fast alternatives which are efficient in these particular scenarios.

Answer 1

There are a number of faster alternatives I've collected over the years that typically rely on a recursive implementation of the function, and bit shifts to handle multiplication when warranted. The following provide functions tailored to integer, float and double. They come with the normal disclaimer: while faster not all possible test have been run and the user should validate input is sane before calling and on return... blah, blah, blah.. But, they are pretty darn useful:

I believe proper attribution goes to Geeks for Geeks Pow(x,n) as pointed out by blue moon. I had long since lost the links.. That looks like them. (minus a tweak or two).

/* Function to calculate x raised to the power y

    Time Complexity: O(n)
    Space Complexity: O(1)
    Algorithmic Paradigm: Divide and conquer.
*/
int power1 (int x, unsigned int y)
{
    if (y == 0)
        return 1;
    else if ((y % 2) == 0)
        return power1 (x, y / 2) * power1 (x, y / 2);
    else
        return x * power1 (x, y / 2) * power1 (x, y / 2);

}

/* Function to calculate x raised to the power y in O(logn)
    Time Complexity of optimized solution: O(logn)
*/
int power2 (int x, unsigned int y)
{
    int temp;
    if (y == 0)
        return 1;

    temp = power2 (x, y / 2);
    if ((y % 2) == 0)
        return temp * temp;
    else
        return x * temp * temp;
}

/* Extended version of power function that can work
for float x and negative y
*/
float powerf (float x, int y)
{
    float temp;
    if (y == 0)
    return 1;
    temp = powerf (x, y / 2);
    if ((y % 2) == 0) {
        return temp * temp;
    } else {
        if (y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}

/* Extended version of power function that can work
for double x and negative y
*/
double powerd (double x, int y)
{
    double temp;
    if (y == 0)
    return 1;
    temp = powerd (x, y / 2);
    if ((y % 2) == 0) {
        return temp * temp;
    } else {
        if (y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}

Answer 2

Non-recursive non-floating point answer

Replace uintmax_t/intmax_t with the type of your desire. Overflow not detected.

uintmax_t powjuu(unsigned x, unsigned y) {
  uintmax_t z = 1;
  uintmax_t base = x;
  while (y) {
    if (y & 1) {  // or y%2
      z *= base;
    }
    y >>= 1; // or y /= 2
    base *= base;
  }
  return z;
}

intmax_t powjii(int x, int y) {
  if (y < 0) {
    switch (x) {
      case 0:
        return INTMAX_MAX;
      case 1:
        return 1;
      case -1:
        return y % 2 ? -1 : 1;
    }
    return 0;
  }
  intmax_t z = 1;
  intmax_t base = x;
  while (y) {
    if (y & 1) {
      z *= base;
    }
    y >>= 1;
    base *= base;
  }
  return z;
}