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
>>> 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
4条答案
按热度按时间w1e3prcc1#
使用decimal模块:
您也可以使用gmpy2 library。
有用的链接:
lh80um4z2#
通常的平方根方法在进行计算之前将参数转换为浮点值。正如您所看到的,这并不适用于非常大的整数。
因此,请使用一个设计用于处理任意大整数的函数。这里是一个,保证返回正确的整数部分的平方根的任何正整数。此函数删除结果的小数部分,这可能是也可能不是您想要的。由于这个函数使用迭代,它也比内置的平方根例程慢。Declare模块处理比内置例程更大的整数,但值的精度必须预先定义,因此它不能处理任意大的值。
2nc8po8w3#
当使用
sqrt
库中的math
时,在进行平方根之前,它会将值转换为浮点数。如果我们手动尝试将
10**2000
转换为浮点数,它也会触发错误如果我们说的是一个很大的数字,但平方等于或小于308,则
Decimal
模块将执行以下操作然而,由于这个数字的平方比308大得多,在这种情况下,2000,人们必须做如下事情
让我们看看如果尝试将
Decimal(10**2000)
转换为float的输出在使用factory时也可以使用decimal模块,因为它们往往会很快变大。
qij5mzcb4#
我建议避免使用decimal模块,因为它涉及到从base 2转换到base 10并返回的额外开销,并且变得不明显需要多少小数精度才能将结果返回到base 2,正确舍入。
如果不使用decimal,计算平方根会稍微麻烦一些,因为这不是内置的功能,但使用
math.isqrt
仍然可以!下面是我提出的一个函数,它可以计算任意整数的平方根,达到任意精度,* 正确舍入 *:更准确地说,以下保证对任何非负整数
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))
(尽管如果最终结果对于浮点数来说太大,这可能会丢失精度或溢出)。将其从整数扩展到任何类型的数字都是微不足道的: