c – The most efficient way to implement an integer based power function pow(int, int)

The Question :

255 people think this question is useful

What is the most efficient way given to raise an integer to the power of another integer in C?

// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125

The Question Comments :
  • When you say “efficiency,” you need to specify efficient in relation to what. Speed? Memory usage? Code size? Maintainability?
  • Doesn’t C have a pow() function?
  • yes, but that works on floats or doubles, not on ints
  • If you’re sticking to actual ints (and not some huge-int class), a lot of calls to ipow will overflow. It makes me wonder if there’s a clever way to pre-calculate a table and reduce all the non-overflowing combinations to a simple table lookup. This would take more memory than most of the general answers, but perhaps be more efficient in terms of speed.
  • pow() not a safe function

The Answer 1

403 people think this answer is useful

Exponentiation by squaring.

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

This is the standard method for doing modular exponentiation for huge numbers in asymmetric cryptography.

The Answer 2

73 people think this answer is useful

Note that exponentiation by squaring is not the most optimal method. It is probably the best you can do as a general method that works for all exponent values, but for a specific exponent value there might be a better sequence that needs fewer multiplications.

For instance, if you want to compute x^15, the method of exponentiation by squaring will give you:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

This is a total of 6 multiplications.

It turns out this can be done using “just” 5 multiplications via addition-chain exponentiation.

n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15

There are no efficient algorithms to find this optimal sequence of multiplications. From Wikipedia:

The problem of finding the shortest addition chain cannot be solved by dynamic programming, because it does not satisfy the assumption of optimal substructure. That is, it is not sufficient to decompose the power into smaller powers, each of which is computed minimally, since the addition chains for the smaller powers may be related (to share computations). For example, in the shortest addition chain for a¹⁵ above, the subproblem for a⁶ must be computed as (a³)² since a³ is re-used (as opposed to, say, a⁶ = a²(a²)², which also requires three multiplies).

The Answer 3

23 people think this answer is useful

If you need to raise 2 to a power. The fastest way to do so is to bit shift by the power.

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)

The Answer 4

14 people think this answer is useful

Here is the method in Java

private int ipow(int base, int exp)
{
    int result = 1;
    while (exp != 0)
    {
        if ((exp &amp; 1) == 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }

    return result;
}

The Answer 5

8 people think this answer is useful

power() function to work for Integers Only

int power(int base, unsigned int exp){

    if (exp == 0)
        return 1;
    int temp = power(base, exp/2);
    if (exp%2 == 0)
        return temp*temp;
    else
        return base*temp*temp;

}

Complexity = O(log(exp))

power() function to work for negative exp and float base.

float power(float base, int exp) {

    if( exp == 0)
       return 1;
    float temp = power(base, exp/2);       
    if (exp%2 == 0)
        return temp*temp;
    else {
        if(exp > 0)
            return base*temp*temp;
        else
            return (temp*temp)/base; //negative exponent computation 
    }

} 

Complexity = O(log(exp))

The Answer 6

7 people think this answer is useful
int pow( int base, int exponent)

{   // Does not work for negative exponents. (But that would be leaving the range of int) 
    if (exponent == 0) return 1;  // base case;
    int temp = pow(base, exponent/2);
    if (exponent % 2 == 0)
        return temp * temp; 
    else
        return (base * temp * temp);
}

The Answer 7

7 people think this answer is useful

An extremely specialized case is, when you need say 2^(-x to the y), where x, is of course is negative and y is too large to do shifting on an int. You can still do 2^x in constant time by screwing with a float.

struct IeeeFloat
{

    unsigned int base : 23;
    unsigned int exponent : 8;
    unsigned int signBit : 1;
};


union IeeeFloatUnion
{
    IeeeFloat brokenOut;
    float f;
};

inline float twoToThe(char exponent)
{
    // notice how the range checking is already done on the exponent var 
    static IeeeFloatUnion u;
    u.f = 2.0;
    // Change the exponent part of the float
    u.brokenOut.exponent += (exponent - 1);
    return (u.f);
}

You can get more powers of 2 by using a double as the base type. (Thanks a lot to commenters for helping to square this post away).

There’s also the possibility that learning more about IEEE floats, other special cases of exponentiation might present themselves.

The Answer 8

6 people think this answer is useful

If you want to get the value of an integer for 2 raised to the power of something it is always better to use the shift option:

pow(2,5) can be replaced by 1<<5

This is much more efficient.

The Answer 9

4 people think this answer is useful

Just as a follow up to comments on the efficiency of exponentiation by squaring.

The advantage of that approach is that it runs in log(n) time. For example, if you were going to calculate something huge, such as x^1048575 (2^20 – 1), you only have to go thru the loop 20 times, not 1 million+ using the naive approach.

Also, in terms of code complexity, it is simpler than trying to find the most optimal sequence of multiplications, a la Pramod’s suggestion.

Edit:

I guess I should clarify before someone tags me for the potential for overflow. This approach assumes that you have some sort of hugeint library.

The Answer 10

2 people think this answer is useful

Late to the party:

Below is a solution that also deals with y < 0 as best as it can.

  1. It uses a result of intmax_t for maximum range. There is no provision for answers that do not fit in intmax_t.
  2. powjii(0, 0) --> 1 which is a common result for this case.
  3. pow(0,negative), another undefined result, returns INTMAX_MAX

    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;
      for (;;) {
        if (y % 2) {
          z *= base;
        }
        y /= 2;
        if (y == 0) {
          break; 
        }
        base *= base;
      }
      return z;
    }
    
    

This code uses a forever loop for(;;) to avoid the final base *= base common in other looped solutions. That multiplication is 1) not needed and 2) could be int*int overflow which is UB.

The Answer 11

1 people think this answer is useful

more generic solution considering negative exponenet

private static int pow(int base, int exponent) {

    int result = 1;
    if (exponent == 0)
        return result; // base case;

    if (exponent < 0)
        return 1 / pow(base, -exponent);
    int temp = pow(base, exponent / 2);
    if (exponent % 2 == 0)
        return temp * temp;
    else
        return (base * temp * temp);
}

The Answer 12

0 people think this answer is useful

One more implementation (in Java). May not be most efficient solution but # of iterations is same as that of Exponential solution.

public static long pow(long base, long exp){        
    if(exp ==0){
        return 1;
    }
    if(exp ==1){
        return base;
    }

    if(exp % 2 == 0){
        long half = pow(base, exp/2);
        return half * half;
    }else{
        long half = pow(base, (exp -1)/2);
        return base * half * half;
    }       
}

The Answer 13

0 people think this answer is useful

I use recursive, if the exp is even,5^10 =25^5.

int pow(float base,float exp){
   if (exp==0)return 1;
   else if(exp>0&amp;&amp;exp%2==0){
      return pow(base*base,exp/2);
   }else if (exp>0&amp;&amp;exp%2!=0){
      return base*pow(base,exp-1);
   }
}

The Answer 14

0 people think this answer is useful

In addition to the answer by Elias, which causes Undefined Behaviour when implemented with signed integers, and incorrect values for high input when implemented with unsigned integers,

here is a modified version of the Exponentiation by Squaring that also works with signed integer types, and doesn’t give incorrect values:

#include <stdint.h>

#define SQRT_INT64_MAX (INT64_C(0xB504F333))

int64_t alx_pow_s64 (int64_t base, uint8_t exp)
{
    int_fast64_t    base_;
    int_fast64_t    result;

    base_   = base;

    if (base_ == 1)
        return  1;
    if (!exp)
        return  1;
    if (!base_)
        return  0;

    result  = 1;
    if (exp &amp; 1)
        result *= base_;
    exp >>= 1;
    while (exp) {
        if (base_ > SQRT_INT64_MAX)
            return  0;
        base_ *= base_;
        if (exp &amp; 1)
            result *= base_;
        exp >>= 1;
    }

    return  result;
}

Considerations for this function:

(1 ** N) == 1
(N ** 0) == 1
(0 ** 0) == 1
(0 ** N) == 0

If any overflow or wrapping is going to take place, return 0;

I used int64_t, but any width (signed or unsigned) can be used with little modification. However, if you need to use a non-fixed-width integer type, you will need to change SQRT_INT64_MAX by (int)sqrt(INT_MAX) (in the case of using int) or something similar, which should be optimized, but it is uglier, and not a C constant expression. Also casting the result of sqrt() to an int is not very good because of floating point precission in case of a perfect square, but as I don’t know of any implementation where INT_MAX -or the maximum of any type- is a perfect square, you can live with that.

The Answer 15

0 people think this answer is useful

I have implemented algorithm that memorizes all computed powers and then uses them when need. So for example x^13 is equal to (x^2)^2^2 * x^2^2 * x where x^2^2 it taken from the table instead of computing it once again. This is basically implementation of @Pramod answer (but in C#). The number of multiplication needed is Ceil(Log n)

public static int Power(int base, int exp)
{
    int tab[] = new int[exp + 1];
    tab[0] = 1;
    tab[1] = base;
    return Power(base, exp, tab);
}

public static int Power(int base, int exp, int tab[])
    {
         if(exp == 0) return 1;
         if(exp == 1) return base;
         int i = 1;
         while(i < exp/2)
         {  
            if(tab[2 * i] <= 0)
                tab[2 * i] = tab[i] * tab[i];
            i = i << 1;
          }
    if(exp <=  i)
        return tab[i];
     else return tab[i] * Power(base, exp - i, tab);
}

The Answer 16

-1 people think this answer is useful

My case is a little different, I’m trying to create a mask from a power, but I thought I’d share the solution I found anyway.

Obviously, it only works for powers of 2.

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;

The Answer 17

-1 people think this answer is useful

In case you know the exponent (and it is an integer) at compile-time, you can use templates to unroll the loop. This can be made more efficient, but I wanted to demonstrate the basic principle here:

#include <iostream>

template<unsigned long N>
unsigned long inline exp_unroll(unsigned base) {
    return base * exp_unroll<N-1>(base);
}

We terminate the recursion using a template specialization:

template<>
unsigned long inline exp_unroll<1>(unsigned base) {
    return base;
}

The exponent needs to be known at runtime,

int main(int argc, char * argv[]) {
    std::cout << argv[1] <<"**5= " << exp_unroll<5>(atoi(argv[1])) << ;std::endl;
}

Add a Comment