The most efficient way to implement an integer based power function pow int int

Question

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

User · Answer

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.

User · Answer

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

User · Answer

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

User · Answer

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  lt  lt  3    8 2    30    1  lt  lt  30    1073741824  A Gigabyte

User · Answer

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  gt  0              return base temp temp          else             return  temp temp  base    negative exponent computation              Complexity   O log exp

User · Answer

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  lt  exp 2                           if tab 2   i   lt   0                  tab 2   i    tab i    tab i               i   i  lt  lt  1                  if exp  lt    i          return tab i        else return tab i    Power base  exp - i  tab

User · Answer

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  gt  gt   1          base    base             return result

User · Answer

Exponentiation by squaring   int ipow int base  int exp        int result   1      for                    if  exp  amp  1              result    base          exp  gt  gt   1          if   exp              break          base    base             return result      This is the standard method for doing modular exponentiation for huge numbers in asymmetric cryptography

User · Answer

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  lt  lt   Exponent - 1   Mask2   Mask1 - 1  return Mask1   Mask2

User · Answer

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  lt stdint h gt    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  gt  gt   1      while  exp            if  base   gt  SQRT INT64 MAX              return  0          base     base           if  exp  amp  1              result    base           exp  gt  gt   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

User · Answer

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  lt  0          return 1   pow base  -exponent       int temp   pow base  exponent   2       if  exponent   2    0          return temp   temp      else         return  base   temp   temp

User · Answer

Late to the party     Below is a solution that also deals with y  lt  0 as best as it can      It uses a result of intmax t for maximum range   There is no provision for answers that do not fit in intmax t    powjii 0  0  -- gt  1 which is a common result for this case  pow 0 negative   another undefined result  returns INTMAX MAX  intmax t powjii int x  int y      if  y  lt  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

User · Answer

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

User · Answer

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  5 above  the subproblem for a6 must be computed as  a      since a   is re-used  as opposed to  say  a6   a   a       which also requires three multiplies

User · Answer

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  lt iostream gt   template lt unsigned long N gt  unsigned long inline exp unroll unsigned base        return base   exp unroll lt N-1 gt  base       We terminate the recursion using a template specialization   template lt  gt  unsigned long inline exp unroll lt 1 gt  unsigned base        return base      The exponent needs to be known at runtime   int main int argc  char   argv          std  cout  lt  lt  argv 1   lt  lt    5     lt  lt  exp unroll lt 5 gt  atoi argv 1     lt  lt   std  endl

User · Answer

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 gt 0 amp  amp exp 2  0         return pow base base exp 2       else if  exp gt 0 amp  amp exp 2  0         return base pow base exp-1

User · Answer

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 lt  lt 5  This is much more efficient

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

Examples related to c

Examples related to algorithm

Examples related to math

Examples related to exponentiation