How do you do *integer* exponentiation in C#?
C#MathIntegerExponentiationC# Problem Overview
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?
C# Solutions
Solution 1 - C#
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.
Solution 2 - C#
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);
Solution 3 - C#
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);
}
Solution 4 - C#
How about:
public static long IntPow(long a, long b)
{
long result = 1;
for (long i = 0; i < b; i++)
result *= a;
return result;
}
Solution 5 - C#
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.
Solution 6 - C#
Use double version, check for overflow (over max int or max long) and cast to int or long?
Solution 7 - C#
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.
Solution 8 - C#
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.
Solution 9 - C#
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.
Solution 10 - C#
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));
}