Fast exponentiation – C# implementation

When you want to power very fast a number in order to meet some performance constraints the standard math power algorithm implementation can be overwhelmed.

Fast exponentiation algorithm take advantage of the computer binary memory structure in order to avoid complexe arithmetic computation.

This algorithm allows you to raise any number to a natural power for a reduced number of multiplications.

For any number x and even degree n , the identity holds:

x ⁿ = (x ^{n / 2} ) ² = x ^{n / 2} ⋅ x ^{n / 2}

For the case of odd degree, it is enough to lower it by one:

x ⁿ = x ^{n – 1} ⋅ x , while (n – 1) is an even number.

Fast exponentiation – recursive implementation (beware of stack overflow)

static long RecursivePower(long x, int n)
{
    if (n == 0) return 1; //in any case Power(x,0) give 1
    if ((n & 1) == 0) //Bit comparison to check if is an even number
    {
        var p = RecursivePower(x, n >> 1); //Equivalent to Power(x, n/2)
        return p * p;
    }
    else
    {
        return x * RecursivePower(x, n - 1);
    }
}

Fast exponentiation – Iterative implementation

static long IterativePower(long x, int n)
{
    var result = 1L;
    while (n> 0)
    {
        if ((n & 1) == 0) //Bit comparison to check if is an even number
        {
            x *= x;
            n >>= 1;
        }
        else
        {
            result *= x;
            --n;
        }
    }
    return result;
}