Python 3中数字大于10 ^ 2000的平方根

Question

我想在Python中计算一个大于10 ^ 2000的数字的平方根.如果我将此数字视为普通整数,我将始终得到此结果:

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

我该如何解决？或者除了使用Python之外是否存在计算此平方根的可能性？

Answer 1

通常的平方根方法在进行计算之前将参数转换为浮点值。如您所见，这不适用于非常大的整数。

因此，请使用旨在处理任意大整数的函数。这是一个，保证返回任何正整数平方根的正确整数部分。此函数删除结果的小数部分，这可能是您想要的，也可能不是。由于此函数使用迭代，因此它也比内置平方根例程慢。Decimal 模块适用于比内置例程更大的整数，但必须提前定义值的精度，因此它不适用于任意大的值。

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

Answer 2

只需使用十进制模块:

>>> from decimal import *
>>> Decimal(10**2000).sqrt()
Decimal('1.000000000000000000000000000E+1000')
>>> Decimal(10**200000).sqrt()
Decimal('1.000000000000000000000000000E+100000')
>>> Decimal(15**35315).sqrt()
Decimal('6.782765081358674922386659760E+20766')

您也可以使用gmpy2库.

>>> import gmpy2
>>> n = gmpy2.mpz(99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999982920000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000726067)
>>> gmpy2.get_context().precision=2048
>>> x = gmpy2.sqrt(n)

有用的链接:

1. 十进制 - Python文档