pythonpython-3.xalgorithmrecursiontail-recursion

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

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.

Solution

• `/` 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 `float`s. Internally these are double-precision floating point numbers which can store up to ~10308 – much smaller than 22147483648/2, hence the `OverflowError`.