在Python 3中大于10 ^ 2000的数字的平方根 [英] square root of a number greater than 10^2000 in Python 3

问题描述

我想在 Python 中计算大于 10^2000 的数字的平方根.如果我将此数字当作普通整数对待，我将始终得到以下结果:

I'd like to calculate the square root of a number bigger than 10^2000 in Python. If I treat this number like a normal integer, I will always get this result back:

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

我该如何解决?还是存在除使用Python之外的其他可能性来计算此平方根?

How do I fix this? Or does a possibilty other than using Python exist to calculate this square root?

推荐答案

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

The usual square root methods convert the parameter to a float value before doing the calculation. As you saw, this does not work well with very large integers.

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

So use a function that is designed to work on arbitrarily large integers. Here is one, guaranteed to return correct integer part of the square root of any positive integer. This function drops the fractional part of the result, which may or may not be what you want. Since this function uses iteration it is also slower than the built-in square root routines. The Decimal module works on larger integers than the built-in routines but the precision of the values must be defined in advance so it does not work on arbitrarily large values.

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

这篇关于在Python 3中大于10 ^ 2000的数字的平方根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！