Power of an integer in C++ [duplicate]

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.

Nullity

A "Warning" is not an "Error". Technically, the C++ standard doesn't know either; it only knows "diagnostics". But while the standard requires diagnostics in certain cases, compiler vendors are free to add more when they think something is fishy. However, that doesn't mean that, if you untended to do something fishy, you're forbidden to do so. Just ask yourself why you do so. (Oh, and the cast should be a static_cast. This is tagged C++, after all.) – Ronnaronnholm

My God, it is full of joke answers! – Dahabeah

Answer 1

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

Unbuild

Linear complexity, dunno if it is worse than the for loop or not :x – Wrecker

Cool, I had no idea the answer to 4^(-2) was "Maximum recursion depth exceeded" (I'm just kidding :p, but it's not hard to add the negative case also) – Offspring

It is worse because it has the same behavior as a for loop plus the function call overhead. – Hades

@Jodi: You assume the compiler does not inline expand the function. Also it looks so cool like that. – Nuptial

@Falaina: whatever the answer to 4^(-2) is, it's not an integer, so negative exponents are not valid inputs. Next you'll be expecting operator/ to give a sensible answer with operand 0... – Raquelraquela

@Martin York: a fair assumption, functions with function calls or loops are generally not inlined by g++, for instance. – Receipt

If you're going to show off with a nifty recursive implementation, at least make it use the O(log(N)) algorithm, and make it tail recursive. – Atmosphere

YAGNI. Not for a week 1 homework assignment, anyway. Extreme programming says, write the first thing that works ;-) – Raquelraquela

@Martin York, @Bill: could the compiler even inline this if it wanted to? It's non-tail recursive call where the depth of recursion is unknown at compile time. – Kamalakamaria

@csj: it's easy enough for the compiler to do a continuation-passing-style transform on it, and then tail-call optimization. – Cassell

just change the parameter to unsigned int p. – Urga

Answer 2

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

Wrecker

Does it cope with negative p? – Nuptial

That's a so typical premature optimization... – Unbuild

@Martin: of course not, it's Savagely Optimized™ – Goraud

Of course you could extend it to if (p == 2) return x * x; if (p == 3) return x * x * x; ... up to 2^32 – Unbuild

+1 for the squaring approach (and I disagree that that's a premature optimization!) But perhaps the return type ought to be "long", to be able to handle larger exponents without overflowing (on platforms where sizeof long > sizeof int). – Tripterous

Choosing the correct algorithm is never a premature optimization, especially when the algorithm is (a) so simple and (b) printed in Knuth. There is no excuse for not knowing and using this particular algorithm. – Atmosphere

@Unbuild - don't be silly - that should be a switch statement ;-) – Fifth

@Martin York: no obviously not, negative powers lead to square roots which are typically not integers. @Jim Lewis: the request was for the return type to be an int. – Wrecker

@MatthieuM. Right conclusion, but wrong reasoning ;) Negative powers don't lead to square roots, but to multiplicative inverses, which typically aren't integers... – Ergocalciferol

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

Cardinalate

I also must admit, that this will not work with older c++ compilers... – Cardinalate

But its still pretty awesome solution :) – Deherrera

+1 for awesome metaprogramming, but -1 because it still linear in P. – Joceline

A newb question: why is the result an enum and not some integer type explicitly? – Enrica

@Enrica Because using template metaprogramming you need to define a different type for each possible power that will be recursively computed during compilation. In this case, to compute 3^7, the compiler will generate the types Pow<3,1>, Pow<3,2>, ..., up to Pow<3,7>, and each of those structs will contain an enum storing the value of 3^1, 3^2, ... and 3^7. Hence, accessing Pow<3,7>::result is later O(1) during execution. There lies the magic of template metaprogramming. – Keynes

Did you really need a specialization for p = 1 ?? – Bastia

When P>1, compiler stops with specialization P=1. Similarly P=0 is there to cover Pow<X,0>. Needs a static_assert (P >= 0, "Only non-negative P can be input"). – Gastrointestinal

P should be unsigned. – Rocaille

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

Fifth

shouldn't it be j <= p in myPow? otherwise for the case of p = 1 you return 1 and not x, which is not correct. – Hartmann

@user931794 - You're right - hopefully it's correct now. – Fifth

You made some great points about recursion; I think that people who have a solid theory background tend to prefer recursive implementations, and those people also tend write higher quality code, but it is wrong to infer that recursion is always "better". Tail call optimization may fail unless you're aware of how it works and know how to check if it's been applied. In the end it's a trade-off between elegance and maybe some stack space. – Hartmann

@user931794 - I think that's a classic case of though A and B are correlated that doesn't prove A causes B, with C (the solid theory background) as a probable common cause. Personally, I think the real issue is that some problems are naturally recursive and others naturally iterative, and then there's my favourites which don't care. For example, the solution could use classic functional list operations (map, filter, fold etc) so the choice of iteration vs. recursion (vs. multicore/distributed implementations etc) is abstracted away. – Fifth

naive non tail recursive: (define (pow1 x n) (if (= n 0) 1 (* x (pow1 x (- n 1))))) tail recursive: (define (pow2 x n) (letrec ((powRec (lambda (k acc) (if (= k 0) acc (powRec (- k 1) (* x acc)))))) (powRec n 1))) higher order: (define (pow3 x n) (fold-left (lambda(a b) (* a b)) 1 (make-list n x))) – Hartmann

This problem is definitely naturally recursive :). The new dawn of the functional paradigm is coming! Say no to side effects, say yes to LISP. – Hartmann

@user931794 - personally, I find pow2 x n = foldr (*) 1 (replicate n x) more readable. OTOH the reason I used a right fold - in Haskell, laziness changes the constant-space recursion rules. Not a problem for this, but IMO pervasive laziness is a bit of a pain. – Fifth

Answer 5

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

Mclellan

I always liked to write it with a for-loop for extra obfuscation :D Here we go: uint64_t res = 1; for (; p; res *= p&1 ? x : 1, x *= x, p >>= 1); – Loewi

Answer 6

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.

Goraud

+1 - Nice suggestion about the for loop. – Chic

A for loop is the last thing you want to use because of its linear complexity, so I suppose this is a joke at the expense of our student ? – Wrecker

@Matthieu: I doubt a student struggling with multiplication will be able to build a logarithmic exponentiation function. Even if somebody wrote one as an answer for him to copy-paste, it would be obvious to the instructor that he didn't write it himself. – Goraud

And now that is exactly what happened. – Dougall

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

Crewel

Answer 8

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.

Avernus

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

Pearlpearla

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

Desiraedesire

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

Jasmin