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.

I am of the opinion is the error is not due to stackoverflow but due to capacity of int datatype to hold large numbers. — Vikramjeet, May 07 '19 at 10:52
You forgot to implement your base case. What happens when n == 1 or 0? — Mad Physicist, May 07 '19 at 11:20
It is unlikely that n/2 or the assignment will error out. Are you sure that this is your actual code? I feel like something is missing here. Perhaps I'm missing something? — Mad Physicist, May 07 '19 at 11:22
@MadPhysicist note that OP is calling the built-in `pow` instead of `myPow` recursively - might be a typo but still worth investigating for future reference — meowgoesthedog, May 07 '19 at 12:19
Does this answer your question? [Why does integer division yield a float instead of another integer?](https://stackoverflow.com/questions/1282945/why-does-integer-division-yield-a-float-instead-of-another-integer) — Karl Knechtel, Feb 13 '23 at 13:44

score 3 · Accepted Answer · answered May 07 '19 at 12:14

/ 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.

score 2 · Answer 2 · answered May 07 '19 at 11:09

2

The size of the value returned post computation is too large to be stored even for a float variable and thus it errors out with OverFlowError Exception

answered May 07 '19 at 11:09

satyam soni

259
1
9

When I typecast the powers to int (which will be without precision loss in this case), the exception doesn't occur. – Vikramjeet May 07 '19 at 11:16

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

2 Answers2