Calculating an exponent in O(log n)

In my algorithms class the teacher challenged us to come up with an algorithm that calculates the value of a base raised to an exponent recursively. Obviously this is quite easy to do in O(n) but he pushed us to figure out a way to do it in O(log n). After playing around a bit I think that I have come up with a good algorithm.


unsigned __int64 exponent(unsigned int base, unsigned int exp)
{
    if (exp < 1)
        return 1;
    else if (exp == 1)
        return base;
    else if (exp % 2 == 0)
    {
        unsigned __int64 retval = exponent(base, exp / 2);
        return retval * retval;
    }
    else
    {
        unsigned __int64 retval = exponent(base, (exp - 1) / 2);
        return base * retval * retval;
    }
}

The algorithm takes advantage of the fact that an x^y = x^(y/2) * x^(y/2). Thus for each cycle it only needs to compute half of the remaining exponent and just multiply it by itself (Since there's only one recursive call for each half we get O(log n) as opposed to O(2^n) if we had done the calls separately). For odd exponents it multiplies the base by the same values computed by the even case. Originally I had it just multiply once like in a linear solution, but this introduced a greater run time for certain exponents. Using a modified version of the even case greatly reduced the number of cycles.

One big caveat is that the data type is limiting. While the algorithm can get the correct result for large exponents, a frequent problem is integer overflow as the algorithm can result in some very large numbers.

Jesse Conner - May 15, 2014 - C++, Code