A Faster Exponentiation Algorithm by Squaring (Power Function)

If we want to compute , we can have a naive implementation by multiplication of base number x.

def pow(x, n):
    r = 1
    for _ in xrange(n):
        r *= x
    return r

This is a O(n) approach, and based on the following, we can reduce the time complexity to .

It can thus be implemented by recursive function.

def pow(x, n):
    if n == 1:
        return x
    if n % 2 == 0:
        return pow(x * x, n // 2)
    return x * pow(x * x, (n - 1) // 2)

Or, a more efficient non-recursive approach can be developed/implemented as such.

def pow(x, n):
    r = 1
    while n > 0:
        if n % 2 == 1:
            r *= x
            n -= 1
        x *= x
        n //= 2
    return r

We can repeatedly reduce the N to either decrement one (if it is odd) or half (it is even). It takes roughtly O(LogN) to reduce N to 1.

References:

[1] http://en.wikipedia.org/wiki/Exponentiation_by_squaring

–EOF (The Ultimate Computing & Technology Blog) —