power of an integer in c++ [duplicate]

A better recursive approach than Zed's.

int myPow(int x, 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).

回答3:

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).

回答4:

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.

回答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.

回答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);
}

回答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.

回答8:

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).

回答9:

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.

回答10:

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;
}

回答11:

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;
}