Integer Exponentiation

Implementation:

This works based on this observation:

$$a^n = a^{n/2} * a^{n/2}$$

BigInteger Pow(BigInteger x,int n)
{
    if(n == 0) return 1;
    else if(n % 2 == 0) {
        var val = Pow(x,n/2);
        return val * val;
    }
    else return x * Pow(x,n-1);
}

How can I improve this? Is there a more efficient algorithm?

• Don't use Egyptian style bracing, that is the style more widely accepted by Java, use the more widely accepted C# bracing style.

Your current structure for the if/else statements is not good. If you have to use braces in the else/elseif statements then you should use bracing everywhere, even on a single operation inside the if statement

like this

BigInteger Pow(BigInteger x,int n)
{
    if(n == 0) 
    {
        return 1;
    }
    else if(n % 2 == 0)
    {
        var val = Pow(x,n/2);
        return val * val;
    }
    else
    {
        return x * Pow(x,n-1);
    }
}

Use if statements like this without the else if

BigInteger Pow(BigInteger x,int n)
{
    if(n == 0) return 1;
    if(n % 2 == 0)
    {
        var val = Pow(x,n/2);
        return val * val;
    }
    return x * Pow(x,n-1);
}

You return inside the if statements so there is no need to else anything just if through because if the first one is true then none of the other if statements will be executed.

I needed to change BigInteger to long. BigInteger it still an INT and so is long, for some reason I could not use BigInteger, so in my equations I will use long

Your naming should definitely be better I went with numBase and numPower I don't normally like hungarian style notation like this, but base is kind of reserved and all.

this is what mine looks like

public static long Pow(long numBase, long numPower)
{
    if (numPower == 0)
    {
        return 1;
    }
    if (numPower % 2 == 0)
    {
        var val = Pow(numBase, numPower / 2);
        return val * val;
    }
    return numBase * Pow(numBase, numPower - 1);
}

also I went with a static method inside of a static class so I could just call it willy-nilly whenever I felt like it. Like this:

Class1.Pow(numBase,numPower);

the only thing with this is that it looks like you are overloading the already created Math.Pow method, you should probably at the least Comment to that effect, and/or create an actual overload for Math.Pow

StackExchange Code Review Q#69399, answer score: 6