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

只用十进制模块：

>>> 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 library。

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

有用的链接：

Decimal - Python Documentation

Answer 2

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

因此请使用专为处理任意大整数而设计的函数。这是一个，保证 return 纠正任何正整数平方根的整数部分。此函数删除结果的小数部分，这可能是也可能不是您想要的。由于此函数使用迭代，因此它也比内置的平方根例程慢。 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 3

当使用库 math 中的 sqrt 时，在对其求平方根之前，它会将值转换为浮点数。

如果我们手动尝试将 10**2000 转换为浮点数，它也会触发错误

>>> float(10**2000)
---------------------------------------------------------------------------
OverflowError                             Traceback (most recent call last)
<ipython-input-14-6ac81f63106d> in <module>
----> 1 math.sqrt(10**2000)

OverflowError: int too large to convert to float

如果我们说的是一个大数，但平方等于或小于 308，Decimal 模块将按如下方式完成工作

>>> from decimal import Decimal
>>> Decimal(math.sqrt(10**308))
Decimal('10000000000000000369475456880582265409809179829842688451922778552150543659347219597216513109705408327446511753687232667314337003349573404171046192448274432')

然而，由于数字的平方远大于 308，在本例中为 2000，因此必须执行以下操作

>>> from decimal import Decimal
>>> Decimal(10**2000).sqrt()
Decimal('1.000000000000000000000000000E+1000')

让我们看看尝试将 Decimal(10**2000) 转换为 float

时的输出

>>> float(Decimal(10**2000))
inf

人们在处理阶乘时也可能会使用 decimal 模块，因为它们往往会很快变大。

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

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

python

python-3.x

large-data

largenumber

square-root