2 minute read

Compute \(x^y\) - Elements of Programming Interviews (EPI)

Problem:

Write a program that takes a double \(x\) and an integer \(y\) and returns \(x^y\). Ignore any overflow and underflow.

Solution:

The naive / brute force approach will be to multiply x by itself y times. Which is \(O(2^n)\) where n is bits needed to represent y.

We can improve on the naive approach by multiplying x by larger values than just \(x\) itself. We notice that if we simply put a loop where we do \(x = x*x\). With each iteration we will increase the exponent of \(x\) by a power of 2. i.e: \(x^2 , x^4, x^8 , x^16 .... x^{2^n}\) with each iteration \(n\). We notice that by doing so we are only limited to visiting the powers of \(x\) that are a power of 2. However, if we break down \(y\) into its binary representation, we can see that at each iteration of our loop we are infact looping over the bits of \(y\). So we can keep a result variable in which we only multiply those powers of \(x\) that correspond to a 1 bit in \(y\). We can take care of negative \(y\) by \(x = frac{1}{x}\) and then with \(y=-y\) carry on the same way as with positive y. An example makes the algorithm much easier to grasp.

Example: \(x = -1.3030347 \\ y = 7 \\ binary(y)= 0111 \\ result = 1\)

  • We have the first power of \(x\) which is \(x\) itself which corresponds to 0 bit of y i.e \(2^0\).
  • Since the \(0^th\) bit of \(y\) is 1 we include this in the result.
  • \[result = result*x = x\]
  • Now we calculate the 2nd power of \(x = x*x = x^2\)
  • we shift \(y\) by 1 bit and then see that \(1^{st}\) bit of \(y\) is 1 so we include this in the result.
  • \[result = result*x = x^3\]
  • \[x = x*x = x^4\]
  • \(y\) \(2^{nd}\) bit is 1
  • \[result = result*x = x^7\]
  • After shifting y we notice that it is 0 now so we stop our loop and output the value of result which is correctly \(x^7\)
def power(x: float, y: int) -> float:
    """Function to calculate x^y"""
    result = 1
    # The idea is that instead of a cache to store the 2 powers of x
    # we instead convert x to its 2 powers and include them into our result as needed
    # based on the binary representation of y.
    # if y is negative then turn x into 1/x and make y positive.
    if y < 0:
        y = -y
        x = 1.0/x
    while y:
        if y & 1:
            result *= x
        x *= x  # x = x*x (x^2) -> (x^4) -> (x^8) -> (x^16)
        y >>= 1
    return result