2
\$\begingroup\$

This is a Leetcode problem:

Implement pow(x, n), which calculates x raised to the power n (\$x^n\$).

Note -

  • -100.0 < x < 100.0

  • n is a 32-bit signed integer, within the range [\$-2^{31}\$, \$2^{31}\$ − 1]

def pow(x, n):
    if n == 0:
        return 1
    if x == 0 and n < 0:
        return
    result = 1
    if n > 0:
        while n > 0:
            pre_result = result
            result *= x
            if pre_result == result or pre_result == -result:
                if result >= 0:
                    return result
                if n % 2 == 0:
                    return -result
                else:
                    return result
            n -= 1
        return result
    else:
        while n < 0:
            pre_result = result
            result /= x
            if pre_result == result or pre_result == -result:
                if result >= 0:
                    return result
                if n % 2 == 0:
                    return -result
                else:
                    return result
            n += 1
        return result

NOTE - My solution is \$O(n)\$.

Here are some example inputs/outputs:

#print(pow(2.00000, 10))

>>> 1024.0

#print(pow(2.10000, 3))

>>> 9.261

#print(pow(2.00000, -2))

>>> 0.25

#print(pow(-1.00000, -2147483648))

>>> 1.0

Here are the times taken for each output:

#%timeit pow(2.00000, 10)

>>> 1.88 µs ± 14 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

#%timeit pow(2.10000, 3)

>>> 805 ns ± 17.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

#%timeit pow(2.00000, -2)

>>> 643 ns ± 9.55 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

#%timeit pow(-1.00000, -2147483648)

>>> 594 ns ± 20 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

So, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

\$\endgroup\$
  • \$\begingroup\$ I'm assuming you're trying to reinvent the wheel here and importing a function from a library is out? \$\endgroup\$ – Mast May 25 at 16:11
  • \$\begingroup\$ Python does has it's own pow() function. \$\endgroup\$ – Mast May 25 at 16:12
  • \$\begingroup\$ @Mast - Yes, according to Leetcode, I am trying to reinvent Python's pow() function. \$\endgroup\$ – Justin May 25 at 16:19
  • \$\begingroup\$ Is your code supposed to work for all -100.0 < x < 100.0 and 32-bit integers n? As an example, pow(10.0, 1000000) returns inf. \$\endgroup\$ – Martin R May 25 at 16:58
  • 1
    \$\begingroup\$ If performance is not important, you could use the hyper operator to get the job done with only doing incrementations. \$\endgroup\$ – dfhwze May 27 at 16:39
5
\$\begingroup\$

Do less writing

You can half the code by using the fact \$x^{-n} = \frac{1}{x^n}\$

if n > 0:
    while n > 0:
    ...
else:
    while n < 0:
    ...

would become

if n < 0:
    # x**(-n) == 1 / x**n
    return 1 / old_code(x, -n)

return old_code(x, n)

(with old code being the code you have from the while loop down)


Likewise \$(-x)^n = x^n\$ if n is even, otherwise \$-(x^n)\$. This extra check can be done at the start rather than in the middle of a loop. Combining the two you get

if n < 0:
    power = -n
else:
    power = n

if x < 0:
    base = -x
else:
    base = x

result = old_code(base, power)

if base != x and power % 2:
    # (-x)**n == -(x**n) if n is odd, otherwise x**n
    result = -result

if power != n:
    # x**(-n) == 1 / x**n
    result = 1 / result

return result

This probably could bit a little nicer, but hopefully it is very clear what is happening. From this you can write your code assuming both the base and power are positive.


Better algorithm

We can improve the algorithm from O(n) to O(log n), where n is the power, using the idea from russian peasant exponentiation. Alternatively you could implement exponentiation by squaring for the same runtime complexity. We can derive the idea by the following observation

$$x^n = \overbrace{x \times x \times x \times \cdots \times x}^{n}$$

$$x^n = \overbrace{x \times x \times x \times \cdots \times x}^{n/2} \times \overbrace{x \times x \times x \times \cdots \times x}^{n/2}$$

$$x^n = y \times y, y = \overbrace{x \times x \times x \times \cdots \times x}^{n/2}$$

We need to make a slight adjustment if n is odd, as n/2 wont be an integer

$$x^n = x \times \overbrace{x \times x \times x \times \cdots \times x}^{\lfloor n/2 \rfloor} \times \overbrace{x \times x \times x \times \cdots \times x}^{\lfloor n/2 \rfloor}$$

$$x^n = x \times y \times y, y = \overbrace{x \times x \times x \times \cdots \times x}^{\lfloor n/2 \rfloor}$$

We can then work out \$x^{n/2}\$ recursively until some easy to compute base case.

Note: To turn this into a loop we can do the same thing, but starting at lower powers and working up. See the pdf for how to continue.

All in all my suggested code would look something like this

def pow(x, n):
    if n == 0:
        return 1
    if x == 1:
        # New easy check
        return 1
    if x == 0:
        if n < 0:
            # builtin pow throws an exception rather than returning None
            raise ZeroDivisionError("...")
        return 0

    if n < 0:
        power = -n
    else:
        power = n

    if x < 0:
        base = -x
    else:
        base = x

    result = _pow(base, power)

    if base != x and power % 2:
        # (-x)**n == -(x**n) if n is odd, otherwise x**n
        result = -result

    if power != n:
        # x**(-n) == 1 / x**n
        result = 1 / result

    return result

def _pow(base, power):
    """Return base**power
    Assume base > 0, power > 0"""
    if power == 1:
        return base

    y = _pow(base, power // 2)
    result = y * y
    if power % 2:
        result *= base
    return result
\$\endgroup\$
  • \$\begingroup\$ Amazing answer! Some really good stuff in there. Your answer has really helped me a lot. Thank you. \$\endgroup\$ – Justin May 25 at 17:29
3
\$\begingroup\$

One obvious thing to do is to take advantage of some math. If you want to calculate 2¹⁶, you don't need to calculate it with 2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2. You could instead calculate it as (2⁸)²=(2⁴)²=((2²)²)². With your approach, you will calculate the value of 2⁸ twice.

Here is a simplified version that shows the idea. You might want to change it to a non-recursive version for performance.

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

And here is code that passes the test and is quicker than 92.14%

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if(n==1):
            return x
        if(x==0 and n<=0):
            return
        if(n==0):
            return 1
        if(n<0):
            return 1/self.myPow(x,-n)
        p = self.myPow(x, n//2)
        ret = p*p
        if(n%2 == 1):
            return ret*x
        return ret

The time complexity here is \$O(log (n))\$

\$\endgroup\$
  • 1
    \$\begingroup\$ Is floor supposed to float? \$\endgroup\$ – Justin May 25 at 16:21
  • \$\begingroup\$ @Justin Don't know. As I said, that was only to show the idea. But I have completed it with working code now. \$\endgroup\$ – klutt May 25 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.