views:

1527

answers:

4

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?

+8  A: 

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.

Vilx-
that's great for a large exponent
orip
Why do you need explicit overflow checking? Won't the built-in C# overflow checking apply just fine? (Assuming you pass /checked)
Jay Bazuzi
+4  A: 

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.

John D. Cook
+4  A: 

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

bh213
How do I know this won't produce incorrect results due to rounding errors?
romkyns
Add 0.5 before converting to int to take care of rounding, as long as the precision of double is greater than that of int or long.
Mark Ransom
Doubles can represent all integers exactly up to 2^53, so this sounds like it will always work.
romkyns
Unless you're using 64-bit integers.
dan04
+4  A: 

Using the math in John Cook's blog link,

    public static long IntPower(int x, short power)
    {
        if (power == 0) return 1;
        if (power == 1) return x;
        // ----------------------
        int n = 15;
        while ((power <<= 1) >= 0) n--;

        long tmp = x;
        while (--n > 0)
            tmp = tmp * tmp * 
                 (((power <<= 1) < 0)? x : 1);
        return tmp;
    }
Charles Bretana