Power of an integer in C++

Question

I need to get the result from pow(a,b) as an integer (both a and b are integers too). Currently, the calculations where (int) pow( (double)a, (double)b) is included are wrong. What could a function be that does the pow(a,b) with integers and returns an integer too?

But here is the odd part: I made my script in Linux with Geany (and g++/GCC compiler) and had just pow(a,b) the script compiled and worked fine.

But in university I have Dev-C++ (and Microsoft Windows). In Dev-C++, the script didn't compile with an error,

[Warning] converting to 'int' from double'

I need to make this script work under Windows (and the MinGW compiler) too.

Answer 1

A better recursive approach than Zed's.

int myPow(int x, unsigned int p)
{
  if (p == 0) return 1;
  if (p == 1) return x;
  
  int tmp = myPow(x, p/2);
  if (p%2 == 0) return tmp * tmp;
  else return x * tmp * tmp;
}

Much better complexity there O(log²(p)) instead of O(p).

Or as a constexpr function using c++17.

template <unsigned int p>
int constexpr IntPower(const int x)
{
  if constexpr (p == 0) return 1;
  if constexpr (p == 1) return x;

  int tmp = IntPower<p / 2>(x);
  if constexpr ((p % 2) == 0) { return tmp * tmp; }
  else { return x * tmp * tmp; }
}

Answer 2

Or you could use a litte bit of template metaprogramming :)

template<int X, int P>
struct Pow
{
    enum { result = X*Pow<X,P-1>::result };
};
template<int X>
struct Pow<X,0>
{
    enum { result = 1 };
};
template<int X>
struct Pow<X,1>
{
    enum { result = X };
};

int main()
{
    std::cout << "pow(3,7) is " << Pow<3,7>::result << std::endl;
    return 0;   
}

This code has the best complexity, O(1), because the evaluation will happen at compile time. Of course this will only work with integer values. However, this function is is only provided for completeness (and fun).

Answer 3

Mostly in reply to Zeds simple recursion...

Why is recursion assumed better than iteration? Especially in C++. What's wrong with...

int myPow (int x, int p) {
  int i = 1;
  for (int j = 1; j <= p; j++)  i *= x;
  return i;
}

I'm not saying your answer is wrong or in any way worse - it's just that I got the impression you think it's good because it's recursive. IMO, in C++ particularly, that bias can lead to slow and even broken programs. Slow programs because you're growing a huge stack, causing cache and virtual memory paging. Broken programs because you get a stack overflow where an iterative solution would work.

Some would look at your answer and think it's tail recursive and would be optimised into iteration anyway. Of course that's not true - after each recursive call exits, there is a multiply still to do, so it is not tail recursive. The thing is, in C++, there are a lot of more subtle things that prevent tail recursion optimisations - even if the compiler does them at all. For example...

void myrecurse (plan *p)
{
  plan i;
  i.prev = p;
  //  more plan setup, checks, and special case handling

  myrecurse (&i);
}

In this case, all the "plan" instances must remain on the stack. Therefore, stack frames cannot be discarded. Therefore this is not optimizable into iteration, even though there are precisely zero operations done after the recursive call. Not even hidden operations like destructor cleanups, since plan is assumed to be a POD struct.

Incidentally, this is based on something I've done in real code - a data structure operation that is planned during the recursion, but nothing is changed in the original nodes until the recursion reaches the root/leaf, all new nodes needed have been successfully allocated, all locks acquired, and there's no curruption to make worse. At that point, an iteration is done through that linked list of plan instances to commit the changes - the logic was clearer as an iteration than being broken up into fragments relating to the unwinding of the recursive calls.

The point here obviously isn't to claim that recursion is automatically bad. It just makes me nervous when people seem to assume recursion is better than iteration by default.

Answer 4

Binary powering, aka exponentiation by squaring.

int powi (int base, unsigned int exp)
{
    int res = 1;
    while (exp) {
        if (exp & 1)
            res *= base;
        exp >>= 1;
        base *= base;
    }
    return res;
}

Note that this returns 1 for powi(0,0).

Answer 5

I assume your homework assignment is to write an integral exponent function. First, take a look at what an exponent is:

http://en.wikipedia.org/wiki/Exponent

Then, look in your textbook for how to multiply numbers in C. You'll want to use a for loop.

Answer 6

Wouldn't a tail-recursive function be best? Something like:

int myPow_helper(int x, int p, int result) {
   if (p == 0) {
      return result;
   } else {
      return myPow_helper(x, p-1, result*x);
   }
}

int myPow(int x, int p) {
   return myPow_helper(x, p, 1);
}

Answer 7

Instead of casting the double to an int in the (int) pow((double)a, (double)b) line, try rounding the results of pow, and then cast to int if necessary.

It's probably one of those floating point problem when you truncate, especially if your result's off by one.

Answer 8

C++ standard doesn't have int pow(int, int) (It has double pow(double, int), float ...). Microsoft's cmath uses C math.h that has not ipow. Some cmath headers define template version of pow.

$ cat main.cpp
#include <cmath>

int main() {
  std::pow(2,2);
}

$ gcc main.cpp # this cmath has template pow
...snip... std::pow<int, int>(int, int)]+0x16): undefined reference to `pow'
collect2: ld returned 1 exit status
1 ;( user@host:
$ gcc main.cpp -lm

Search for function:ipow lang:c++ on Google Code .

Here's example from the first link:

template <typename Type1, typename Type2>
Type1 ipow(Type1 a, Type2 ex)
// Return a**ex
{
    if ( 0==ex )  return 1;
    else
    {
        Type1 z = a;
        Type1 y = 1;
        while ( 1 )
        {
            if ( ex & 1 )  y *= z;
            ex /= 2;
            if ( 0==ex )  break;
            z *= z;
        }
        return y;
    }
}

See calculating integer powers (squares, cubes, etc.) in C++ code.

Answer 9

Why linearly? Try it logarithmic!!

long long powx( int val, int exp )
{
    long long actual = val;
    long long prod = 1;
    int i;

    for ( i = 0; i < 32; i++ )
    { 
        if ( exp & 0x1 )
        {
            prod *= actual;
        }

        exp >>= 1;

        actual *= actual;
    }

    return prod;
}

Answer 10

There are two alternatives here, when we want to count power(a,n) we may write code which is very short and works in O(logn) time, but is recursively and therefore requires creating new stackframe for each call and needs a bit more time than loop iteration. So short code is:

int power(int a, int n){
    if(n == 0) return 1;
    int keep = power(a,n/2);
    if(n & 1) return keep*keep*a;   // (n & 1) is and operation of 1 and the 
    return keep*keep;               // last bit of n
}

and as for the faster code, here it is using while loop:

int power(int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1)
            res *= a;
        a *= a;
        n >>= 1;
    }
    return res;
}

Answer 11

A nice recursive approach you can show off:

int myPow(int x, int p) {
  if (p == 0) return 1;
  if (p == 1) return x;
  return x * myPow(x, p-1);
}