power of an integer in c++ [duplicate]

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

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

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.

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.

power of an integer in c++ [duplicate]

Related

Recent Posts