Python Sqrt限制？

Question

我正在处理非常大的数字（1000000位），我需要计算它们的平方根。我的代码似乎达到了极限。

y = 10**309
x = y**0.5
print(x)

我得到一个错误：

x = y**0.5
OverflowError: int too large to convert to float

代码有效期至10**308。但除此之外，它似乎破碎了。我也在命令行中检查了这一点。同样的错误。有人能帮我吗？

如果这是python的限制，是否有其他方法可以使用？

编辑：进行代码更正。

Answer 1

基于我认为类似的问题，您可以研究使用Decimal类。

这里有一个例子使用你所拥有的

    >>> x = 10**309
    >>> y =x**.5
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    OverflowError: long int too large to convert to float
    >>> import decimal
    >>> d = decimal.Decimal(x)
    >>> d.sqrt()
    Decimal('3.162277660168379331998893544E+154')
    >>> float(d.sqrt())
    3.1622776601683792e+154
    >>> 

可能会有帮助，它不会给你错误。

Answer 2

您应该使用gmpy2模块（https://code.google.com/p/gmpy/）。它提供了非常快的多精度算法。

在我的系统中，百万位数的运算速度非常快。

In [8]: a=gmpy2.mpz('3'*1000000)
In [9]: %timeit gmpy2.isqrt(a)
10 loops, best of 3: 22.8 ms per loop
In [10]: %timeit (a+1)*(a-1)
10 loops, best of 3: 20.9 ms per loop

处理100000000位数字只需几秒钟。

In [20]: a.num_digits(10)
Out[20]: 99995229
In [21]: %timeit gmpy2.isqrt(a)
1 loops, best of 3: 5.05 s per loop
In [22]: %timeit (a+1)*(a-1)
1 loops, best of 3: 3.49 s per loop

免责声明：我是gmpy2的当前维护者。

Answer 3

用一点数学知识简化你的问题。

请注意，sqrt（a*b）=sqrt（a）*sqrt（b）（至少对于实数、正数）。

所以，任何大于10^100的数，除以10^100。那是a，除法的结果是b，这样你的原始数=a*b。然后用10^100 (= 10^50)的平方根，乘以b的平方根，你就有了答案。

以你的例子：

import math
x = 10**309
a = 1e100
b = 1e209   # Note: you can't calculate this within Python; just use plain math here
y = 1e50 * math.sqrt(1e209)

不太圆的数字示例：

x = 3.1415 * 1e309
a = 1e100
b = 3.1415e209   # Again, just subtract the exponent: 309 - 100
y = 1e50 * math.sqrt(3.1415e209)

或者对于不是10的幂的整数，完全写出：

x = 707070
x = 70.707 * 1e4  # note: even number in exponent
x = 70.707e4
a = 1e2  # sqrt(1e2) = 1e1 = 10
b = 70.707e2
y = 10 * sqrt(70.707e2)

几点注意事项

>

Python处理大得离谱的整数没有问题。对于浮点数，它使用标准（C）约定，并将自身限制为64位精度。当取某事物的平方根时，几乎总是得到浮点数。

1e309表示10**309，3.1415e209表示3.1415 * 10**209。这是一个标准的编程约定。