power of an integer in c++

Question

Hi!

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. Maybe someone can help with a function 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 MS Windows). In Dev-C++ the script didn't compile with an error [Warning] converting to int' from double'

I need to make this scrpit work under Windows (and Mingw compiler) too.

Thanks in advance,

-skazhy

Answer 1

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 2

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

Answer 3

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 4

A better recursive approach than Zed's, don't know why you failed so closed Zed :x

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). I should add that this really is a classic...

Answer 5

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 6

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 7

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 8

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.