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

gijlo24d  于 2023-10-14  发布在  Python
关注(0)|答案(4)|浏览(114)

我想在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之外,是否存在其他可能性来计算这个平方根?

w1e3prcc

w1e3prcc1#

使用decimal模块:

>>> 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)

有用的链接:

  1. Decimal - Python Documentation
lh80um4z

lh80um4z2#

通常的平方根方法在进行计算之前将参数转换为浮点值。正如您所看到的,这并不适用于非常大的整数。
因此,请使用一个设计用于处理任意大整数的函数。这里是一个,保证返回正确的整数部分的平方根的任何正整数。此函数删除结果的小数部分,这可能是也可能不是您想要的。由于这个函数使用迭代,它也比内置的平方根例程慢。Declare模块处理比内置例程更大的整数,但值的精度必须预先定义,因此它不能处理任意大的值。

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
2nc8po8w

2nc8po8w3#

当使用sqrt库中的math时,在进行平方根之前,它会将值转换为浮点数。
如果我们手动尝试将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

在使用factory时也可以使用decimal模块,因为它们往往会很快变大。

qij5mzcb

qij5mzcb4#

我建议避免使用decimal模块,因为它涉及到从base 2转换到base 10并返回的额外开销,并且变得不明显需要多少小数精度才能将结果返回到base 2,正确舍入。
如果不使用decimal,计算平方根会稍微麻烦一些,因为这不是内置的功能,但使用math.isqrt仍然可以!下面是我提出的一个函数,它可以计算任意整数的平方根,达到任意精度,* 正确舍入 *:

from fractions import Fraction

def sqrt_int(x: int, precision: int = 53) -> Fraction:
    n = max(precision - 1 - ((x.bit_length() - 1) >> 1), 0)
    xp2n = x << (n << 1)
    n0 = math.isqrt(xp2n)
    n1 = n0 + 1
    return Fraction(n1 if n0 * n1 < xp2n else n0, 1 << n)

更准确地说,以下保证对任何非负整数x成立:

  • |√(x) - sqrt_int(x, p)| < 0.5ulpₚ(√(x))
  • float(sqrt_int(x, 53)) == math.sqrt(x)只要math.sqrt(x)不提升OverflowError
  • sqrt_int(x * x) == x,避免this problem

如果你需要的结果是float而不是Fraction,只需要执行float(sqrt_int(x))(尽管如果最终结果对于浮点数来说太大,这可能会丢失精度或溢出)。
将其从整数扩展到任何类型的数字都是微不足道的:

def sqrt(x: int | float | Decimal | Fraction, precision: int = 53) -> Fraction:
    x = Fraction(x)
    return sqrt_int(x.numerator, precision) / sqrt_int(x.denominator, precision)

相关问题