CODEWITHSUNDEEP
c#mathintegerexponentiation
Roman Starkov
Roman Starkov

Reputation: 61422

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

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?

Upvotes: 75

Views: 75085

Answers (11)

teichert
teichert

Reputation: 4713

Expounding slightly on Jeppe Stig Nielsen's comment, BigInteger.Pow can be used:

long result = (long) System.Numerics.BigInteger.Pow(7, 19);

It is nice since it avoids rounding errors that would happen with Math.Pow for large numbers and doesn't fail loudly on overflow:

Console.WriteLine((long) System.Numerics.BigInteger.Pow(7, 19));
Console.WriteLine((long) Math.Pow(7, 19)); 
Console.WriteLine((int) Math.Pow(7, 19)); 
Console.WriteLine((int) System.Numerics.BigInteger.Pow(7, 19));

Output:

11398895185373143
11398895185373144
-2147483648
Value was either too large or too small for an Int32.

Upvotes: 3

SunsetQuest
SunsetQuest

Reputation: 8827

Very interesting.. as of .net 5.0 SimplePower() is now 350X faster. And I would say best in portability/performance/readability...

    public static int SimplePower(int x, int pow)
    {
        return (int)Math.Pow(x, pow);
    }

Here is another one I built in the past that is was fast...

    public static int PowerWithSwitch(int x, int pow)
    {
        switch ((uint)pow)
        {
            case 0: return 1;
            case 1: return x;
            case 2: return x * x;
            case 3: return x * x * x;
            case 4: { int t2 = x * x; return t2 * t2; }
            case 5: { int t2 = x * x; return t2 * t2 * x; }
            case 6: { int t3 = x * x * x; return t3 * t3; }
            case 7: { int t3 = x * x * x; return t3 * t3 * x; }
            case 8: { int t3 = x * x * x; return t3 * t3 * x * x; }
            case 9: { int t3 = x * x * x; return t3 * t3 * t3; }
            case 10: { int t3 = x * x * x; return t3 * t3 * t3 * x; }
            case 11: { int t3 = x * x * x; return t3 * t3 * t3 * x * x; }
            case 12: { int t3 = x * x * x; return t3 * t3 * t3 * t3; }
            case 13: { int t3 = x * x * x; return t3 * t3 * t3 * t3 * x; }
            case 14: { int t4 = x * x * x * x; return t4 * t4 * t4 * x * x; }
            case 15: { int t4 = x * x * x * x; return t4 * t4 * t4 * x * x * x; }
            case 16: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4; }
            case 17: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * x; }
            case 18: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * x * x; }
            case 19: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * x * x * x; }
            case 20: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4; }
            case 21: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * x; }
            case 22: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * x * x; }
            case 23: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * x * x * x; }
            case 24: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * t4; }
            case 25: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * t4 * x; }
            case 26: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * t4 * x * x; }
            case 27: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * t4 * x * x * x; }
            case 28: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * t4 * t4; }
            case 29: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * t4 * t4 * x; }
            default:
                if (x == 0)
                    return 0;
                else if (x == 1)
                    return 1;
                else
                    return (x % 1 == 0) ? int.MaxValue : int.MinValue;
        }
        return 0;
    }

Performance testing (.Net 5)

  • MathPow(Sunsetquest) : 11 ms (.net 4 = 3693ms ) <- 350x faster!!!

  • PowerWithSwitch(Sunsetquest): 145 ms (.net 4 = 298 ms )

  • Vilx : 148 ms (.net 4 = 320 ms )

  • Evan Moran-recursive divide : 249 ms (.net 4 = 644 ms )

  • mini-me : 288 ms (.net 4 = 194 ms )

  • Charles Bretana(aka Cook's) : 536 ms (.net 4 = 950 ms )

  • LINQ Version : 4416 ms(.net 4 = 3693 ms)

(testing notes: AMD Threadripper Gen1, .Net 4 & 5, release build, no debugger attached, bases:0-100k, exp:0-10)

Note: Little accuracy checking was done in the above tests.

Upvotes: 10

High
High

Reputation: 626

Another way is:

int Pow(int value, int pow) {
    var result = value;
    while (pow-- > 1)
        result *= value;
    return pow == 0 ? result : pow == -1 ? 1 : throw new ArgumentOutOfRangeException(nameof(pow));
}

Upvotes: 0

mini-me
mini-me

Reputation: 147

How about:

public static long IntPow(long a, long b)
{
  long result = 1;
  for (long i = 0; i < b; i++)
    result *= a;
  return result;
}

Upvotes: 12

Ralph
Ralph

Reputation: 11

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.

Upvotes: 0

Charles Bretana
Charles Bretana

Reputation: 146499

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

to address objection that the code will not work if you change the type of power, well... leaving aside the point that anyone who changes code they don't understand and then uses it without testing.....
but to address the issue, this version protects the foolish from that mistake... (But not from a myriad of others they might make) NOTE: not tested.

    public static long IntPower(int x, short power)
    {
        if (power == 0) return 1;
        if (power == 1) return x;
        // ----------------------
        int n = 
            power.GetType() == typeof(short)? 15:
            power.GetType() == typeof(int)? 31:
            power.GetType() == typeof(long)? 63: 0;  

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

Also try this recursive equivalent (slower of course):

    public static long IntPower(long x, int power)
    {
        return (power == 0) ? x :
            ((power & 0x1) == 0 ? x : 1) *
                IntPower(x, power >> 1);
    }

Upvotes: 21

Claudio
Claudio

Reputation: 652

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.

Upvotes: 0

3dGrabber
3dGrabber

Reputation: 5074

LINQ anyone?

public static int Pow(this int bas, int exp)
{
    return Enumerable
          .Repeat(bas, exp)
          .Aggregate(1, (a, b) => a * b);
}

usage as extension:

var threeToThePowerOfNine = 3.Pow(9);

Upvotes: 64

Evan Moran
Evan Moran

Reputation: 4173

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.

Upvotes: 2

Vilx-
Vilx-

Reputation: 106920

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.

Upvotes: 68

bh213
bh213

Reputation: 6529

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

Upvotes: 3

Related Questions