How do you do *integer* exponentiation in C#?

Question

The built-in Math.Pow() function in .NET raises a double base to a double exponent and returns a double result.

What's the best way to do the same with integers?

Added: It seems that one can just cast Math.Pow() result to (int), but will this always produce the correct number and no rounding errors?

Answer 1

My favorite solution to this problem is a classic divide and conquer recursive solution. It is actually faster then multiplying n times as it reduces the number of multiplies in half each time.

public static int Power(int x, int n)
{
  // Basis
  if (n == 0)
    return 1;
  else if (n == 1)
    return x;

  // Induction
  else if (n % 2 == 1)
    return x * Power(x*x, n/2);
  return Power(x*x, n/2);
}

Note: this doesn't check for overflow or negative n.

Answer 2

Here's a blog post that explains the fastest way to raise integers to integer powers. As one of the comments points out, some of these tricks are built into chips.

Answer 3

Use double version, check for overflow (over max int or max long) and cast to int or long?

Answer 4

For a short quick one-liner.

int pow(int i, int exp) => (exp == 0) ? 1 : i * pow(i, exp-1);

There are no negative exponent nor overflow checks.

Answer 5

A pretty fast one might be something like this:

int IntPow(int x, uint pow)
{
    int ret = 1;
    while ( pow != 0 )
    {
        if ( (pow & 1) == 1 )
            ret *= x;
        x *= x;
        pow >>= 1;
    }
    return ret;
}

Note that this does not allow negative powers. I'll leave that as an exercise to you. :)

Added: Oh yes, almost forgot - also add overflow/underflow checking, or you might be in for a few nasty surprises down the road.

Answer 6

I cast the result into int, like this:

double exp = 3.0;
int result = (int)Math.Pow(2.0, exp);

In this case, there are no rounding errors because base and exponent are integer. The result will be integer too.