OverflowError: (34, 'Numerical result out of range') in writing a custom implementation of pow(x,n)

Question

While implementing pow(x, n), for (x=2,and n=-2147483648), I am getting the below error:

Code :

class Solution:
    def myPow(self, x, n):
        flag = n < 0
        n = -1 * n if flag else n
        ans = None
        if n % 2 == 0:
            t = pow(x, n/2)
            ans = t*t
        else:
            t = pow(x, (n-1)/2)
            ans = x * t * t
        return (1/ans) if flag else ans

if __name__ == "__main__":
    Solution().myPow(2,-2147483648)

---

Traceback (most recent call last):
  File "pw.py", line 16, in <module>
    Solution().myPow(2,-2147483648)
  File "pw.py", line 8, in myPow
    t = pow(x, n/2)
OverflowError: (34, 'Numerical result out of range')

However, when i implement the same with n/2 and (n-1)/2 typecasted into int as below code snippet I get 0.0 as the output:

class Solution:
    def myPow(self, x, n):
        flag = n < 0
        n = -1 * n if flag else n
        ans = None
        if n % 2 == 0:
            t = pow(x, int(n/2))
            ans = t*t
        else:
            t = pow(x, int((n-1)/2))
            ans = x * t * t
        return (1/ans) if flag else ans

if __name__ == "__main__":
    Solution().myPow(2,-2147483648)

I am unable to figure out the cause.Is this due to stackoverflow since python interpreter doesn't handle tail recursion optimization, and the result returned is persisted since it is being used later for further calculations.

I am curious to know why the two cases differ.

Answer 1

/ in Python 3.x always performs floating point division, unlike in Python 2.x where the operands had to be explicitly casted. Therefore type(n/2) == float whereas type(int(n/2)) == int. Alternatively you could use n // 2 where // performs floor/integer division.

The built-in pow function returns a float if either of the arguments are also floats. Internally these are double-precision floating point numbers which can store up to ~10³⁰⁸ – much smaller than 2^2147483648/2, hence the OverflowError.