square root of a number greater than 10^2000 in Python 3

Question

I'd like to calculate the square root of a number bigger than 10^2000 in Python. If I treat this number like a normal integer, I will always get this result back:

Traceback (most recent call last):
  File "...", line 3, in <module>
    print( q*(0.5)  )
OverflowError: int too large to convert to float

How do I fix this? Or does a possibilty other than using Python exist to calculate this square root?

Answer 1

The usual square root methods convert the parameter to a float value before doing the calculation. As you saw, this does not work well with very large integers.

So use a function that is designed to work on arbitrarily large integers. Here is one, guaranteed to return correct integer part of the square root of any positive integer. This function drops the fractional part of the result, which may or may not be what you want. Since this function uses iteration it is also slower than the built-in square root routines. The Decimal module works on larger integers than the built-in routines but the precision of the values must be defined in advance so it does not work on arbitrarily large values.

import math

_1_50 = 1 << 50  # 2**50 == 1,125,899,906,842,624

def isqrt(x):
    """Return the integer part of the square root of x, even for very
    large integer values."""
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    if x < _1_50:
        return int(math.sqrt(x))  # use math's sqrt() for small parameters
    n = int(x)
    if n <= 1:
        return n  # handle sqrt(0)==0, sqrt(1)==1
    # Make a high initial estimate of the result (a little lower is slower!!!)
    r = 1 << ((n.bit_length() + 1) >> 1)
    while True:
        newr = (r + n // r) >> 1  # next estimate by Newton-Raphson
        if newr >= r:
            return r
        r = newr