Teaching Kids Programming – Logarithm Algorithm to Compute the Power x^n Function

Teaching Kids Programming: Videos on Data Structures and Algorithms

Implement pow(x, n), which calculates x raised to the power n (i.e. xn).

Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: pow(2, -1) = 1/pow(2, 2) = 1/4 = 0.25

O(N) Power Function

The bruteforce (most straightforward) solution is to multiple the base (x) exponential (n) times. Special cases can be determined when base is 0, or 1, or the exponential is zero. If the exponential is negative, we can convert the computation to (1.0/x)^(-n).

1
2
3
4
5
6
7
8
9
10
11

def pow(x, n):
    if x == 1 or n == 0:
        return 1
    if x == 0:
        return 0
    if n < 0:
        x, n = 1.0/x, -n
    ans = 1
    for _ in range(n):
        ans *= x
    return ans

def pow(x, n):
    if x == 1 or n == 0:
        return 1
    if x == 0:
        return 0
    if n < 0:
        x, n = 1.0/x, -n
    ans = 1
    for _ in range(n):
        ans *= x
    return ans

Logarithm Pow Function

Because we have the following:

when n is odd.
And when n is even.

Thus, we can use this to reduce the complexity to O(LogN). The following is a recursive implementation of such logarithm algorithm to compute the Math Pow function (base, exponential)

1
2
3
4
5
6
7
8
9
10
11

def pow(x, n):
    if x == 1 or n == 0:
        return 1
    if x == 0:
        return 0
    if n < 0:
        x, n = 1.0/x, -n
    if n & 1:
        return x * pow(x, n - 1)
    y = pow(x, n//2)
    return y * y

def pow(x, n):
    if x == 1 or n == 0:
        return 1
    if x == 0:
        return 0
    if n < 0:
        x, n = 1.0/x, -n
    if n & 1:
        return x * pow(x, n - 1)
    y = pow(x, n//2)
    return y * y

Alternatively, we can do this iteratively. The base is squared and the exponential is reduced to half. For example, 2^4 = 4^2 because 2^(2^2) = (2^2)^2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def pow(x, n):
    if x == 1 or n == 0:
        return 1
    if x == 0:
        return 0
    if n < 0:
        x, n = 1.0/x, -n
    ans = 1
    while n >= 1:
        if n & 1:
            ans *= x
        x *= x
        n >>= 1
    return ans

def pow(x, n):
    if x == 1 or n == 0:
        return 1
    if x == 0:
        return 0
    if n < 0:
        x, n = 1.0/x, -n
    ans = 1
    while n >= 1:
        if n & 1:
            ans *= x
        x *= x
        n >>= 1
    return ans

Also, remember, in Python, the above could be simply replaced by the following ** operator:

1
2

def pow(x, n):
   return x**n

def pow(x, n):
   return x**n

–EOF (The Ultimate Computing & Technology Blog) —