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?

As written elsewhere, since 2010 (.NET 4.0) there is [`BigInteger.Pow` method](http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.pow.aspx) which does integer exponentiation (needs assembly reference to System.Numerics.dll). — Jeppe Stig Nielsen, Feb 13 '14 at 07:41

Vilx- · Accepted Answer · 2008-12-20T19:41:35.380

66

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.

edited Dec 20 '08 at 19:41

answered Dec 20 '08 at 18:45

Vilx-

104,512
87
279
422

that's great for a large exponent – orip Dec 20 '08 at 18:53
1

Why do you need explicit overflow checking? Won't the built-in C# overflow checking apply just fine? (Assuming you pass /checked) – Jay Bazuzi Dec 20 '08 at 21:06
3

The algorithmic name for this is exponentiation by repeated squaring. Essentially, we repeatedly double x, and if pow has a 1 bit at that position, we multiply/accumulate that into the return value. – ioquatix Nov 23 '12 at 10:49
Using .NET 4's BigInteger makes for really big integer powers – bugmagnet Aug 09 '13 at 06:21
2

@boost BigInteger has powering built in though – harold Oct 04 '13 at 08:45
That's fantastic! I always wondered how powers were best computed since the naive algorithm for it has lousy time complexity. This one is guaranteed to return within 32 iterations (and average case will be a lot lower). And if you re-implement it for longs, it will only double the max iterations. – Miles B. Jan 30 '19 at 19:28
1

@MilesB. - Mind you, with Int32 you're not going to get anything higher than to the 32nd power, so the naive algorithm would be just fine anyway. :) In fact the same goes for Int64 - 64 iterations really isn't that much, especially since modern CPUs will perform it all in the CPU cache or even registers. The speed benefits from this fancy algorithm will only be noticeable under some very exotic conditions. – Vilx- Jan 30 '19 at 19:45
1

@Vilx - True enough. I'm just a bit paranoid when it comes to efficiency... – Miles B. Jan 30 '19 at 20:06
1

@MilesB. Fair enough. :) I used to be like that too. But then I came to work on some code that did some mind-blowing work in some pretty average Javascript code (browser side) and I realized that modern computers are pretty efficient already. Unless you actually do something unnecessarily complicated, it will almost always work just fine without meticulous optimizations. And the few places where it doesn't - you can take care of them on a case-by-case basis. – Vilx- Jan 30 '19 at 20:56
3

@MilesB. These days my priority is to make my code as readable and easily-understandable as possible. No mind-boggling clever optimizations; no "magic" constructs that perform complex things implicitly without any visible code; etc. Fascinatingly, performance problems are rare. – Vilx- Jan 30 '19 at 21:03

3dGrabber · Answer 2 · 2015-01-08T14:01:35.453

61

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

edited Jan 08 '15 at 14:01

answered Aug 09 '12 at 09:43

3dGrabber

4,710
1
34
42

23

This is the most hilarious answer I've seen today - congratulations on making it work as expected :D – ioquatix Nov 23 '12 at 09:37
5

@ioquatix that's how you'd do it in a functional programming language, with a straight face. – Martin Capodici Aug 11 '15 at 21:21
3

@MartinCapodici I'm always smiling when I write code. Either that or I sometimes grimace when reading other peoples code. I don't usually have a straight face :) – ioquatix Aug 13 '15 at 00:44

Charles Bretana · Answer 3 · 2016-04-03T15:10:03.820

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

Make sure if you use this to not modify it at all. I thought I'd get around using a `short` to avoid casting anything, but the algorithm doesn't work if it's not. I prefer the more straightforward if less performant method by Vilx — Eric Stassen, Nov 18 '11 at 01:00
obsidian, You may be able to use an int if you change the 15 in the algorithm to a 31 — Charles Bretana, Jan 07 '12 at 23:20
I did a brief benchmark and as I suspected, Vilx's method is more efficient if you need int-length powers (approximately 6 times faster). Perhaps someone else can verify this result? — ioquatix, Nov 23 '12 at 11:03
HEADS UP -- Like Obsidian said, this does not work if you CHANGE THE TYPE OF POWER. Sorry for all caps but seems like it really really should be called out. — pfrank, Apr 01 '16 at 23:44
YES IT DOES... (you just have to change the value 15 to the length of the type used in the exponent.) — Charles Bretana, Apr 03 '16 at 14:47

score 12 · Answer 4 · edited Feb 05 '20 at 22:14

12

How about:

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

edited Feb 05 '20 at 22:14

mklement0

382,024
64
607
775

answered Apr 11 '12 at 15:28

mini-me

147
1
2

Simple, though a check for negative `b` is called for. – mklement0 Feb 05 '20 at 22:15
1

Note that this code's time complexity is O(n) where n is the power, whereas in the top answer it's O(log(n)), which is much better for large powers. – Bip901 Dec 10 '20 at 12:49

SunsetQuest · Answer 5 · 2020-12-12T20:00:52.977

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.

mini-me's performance would only hold for smaller powers. But I'm definitely using your code to help solve Problem 43: https://projecteuler.net/problem=43 — turiyag, Dec 28 '14 at 12:49
Running exponents from 0 - 30 for bases from 0 - 1M and Vilx- is 2x faster; for exponents from 0 - 100 it is 4x faster. — NetMage, May 07 '19 at 22:07

score 3 · Answer 6 · answered Dec 20 '08 at 18:52

3

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

answered Dec 20 '08 at 18:52

bh213

6,343
9
43
52

1

How do I know this won't produce incorrect results due to rounding errors? – Roman Starkov Dec 20 '08 at 20:27
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 Dec 20 '08 at 21:53
1

Doubles can represent all integers exactly up to 2^53, so this sounds like it will always work. – Roman Starkov Dec 21 '08 at 08:15
1

Unless you're using 64-bit integers. – dan04 May 01 '10 at 05:01

score 2 · Answer 7 · answered Jul 01 '11 at 22:25

2

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.

answered Jul 01 '11 at 22:25

Evan Moran

3,825
34
20

3

This is the same algorithm as Vilx-, except it uses much more space (the recursive call is not a tail call). – Ben Voigt Jun 25 '12 at 21:06

High · Answer 8 · 2020-06-09T12:45:50.827

1

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

edited Jun 09 '20 at 12:45

answered Jun 09 '20 at 12:14

High

606
1
6
19

score 0 · Answer 9 · answered May 08 '15 at 13:26

0

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.

answered May 08 '15 at 13:26

Claudio

642
3
12

3

Try Math.Pow(7, 19). There are float related errors. – N-ate Aug 05 '15 at 21:08
2

@N-ate `7^19` is way too big for an Int32 anyway, so you won't be casting to an int if you know your numbers are this big. – Bip901 Dec 10 '20 at 12:53

score 0 · Answer 10 · answered Sep 02 '17 at 15:32

0

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.

answered Sep 02 '17 at 15:32

Ralph

1
1

score 0 · Answer 11 · answered Feb 23 '23 at 00:28

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.

How do you do integer exponentiation in C#?

11 Answers11

Linked

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

11 Answers11

Linked

How do you do integer exponentiation in C#?