Why this python code throw OverflowError?

Question

Today, I was doing the leetcode 50 MyPow , and I decided to use the recursion to achieve it. My code is as follows:

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n > 0:
            return self.recur(x, n)
        else:
            return 1.0 / self.recur(x, -n)

    def recur(self, x: float, n: int) -> float:
        if n == 0:
            return 1.0
        else:
            y = self.recur(x, n // 2) ** 2
            return y if n % 2 == 0 else y * x

But this code doesn't work and output the error:

OverflowError: (34, 'Numerical result out of range')
  [Previous line repeated 19 more times]
    y = self.recur(x, n // 2) ** 2
Line 13 in recur (Solution.py)
    y = self.recur(x, n // 2) ** 2
Line 13 in recur (Solution.py)
    y = self.recur(x, n // 2) ** 2
Line 13 in recur (Solution.py)
    return 1.0 / self.recur(x, -n)
Line 7 in myPow (Solution.py)
    ret = Solution().myPow(param_1, param_2)
Line 40 in _driver (Solution.py)
    _driver()
Line 51 in <module> (Solution.py)

Then I try to modify these lines :

            y = self.recur(x, n // 2) ** 2
            return y if n % 2 == 0 else y * x

to

            y = self.recur(x, n // 2) 
            return y*y if n % 2 == 0 else y *y* x

Finally, it worked. But why? And what about the difference between them?

Add the failed case:

x = 2.00000
n = -2147483648

Is someone who can answer my confusion?

Answer 1

This is because the multiplication returns inf when the result doesn't fit in the float type, while the power ** throws an exception. For example, this prints inf:

r = 1.0
for _ in range(350):
    r = r * 10.0
print(r)

while this throws an OverflowError:

print(10.0 ** 350)

There's probably some explanation of this in PEPs, but I'm not aware of it.

As pointed out in the comments, you need an arbitrary precision type here, not a float. Consider:

from decimal import Decimal

x = Decimal(10.0)
p = 350

r = Decimal(1.0)
for _ in range(350):
    r = r * x
print(r)

print(x ** 350)

This would print the result correctly.