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

通常の平方根方法は、計算を行う前に、float値にパラメータを変換します。あなたが見たように、これは非常に大きな整数ではうまく動作しません。

したがって、任意の大きな整数で動作するように設計された関数を使用してください。正の整数の平方根の正しい整数部分を返すことが保証されています。この関数は、結果の小数部分を削除します。この関数は反復を使用するので、組み込みの平方根ルーチンよりも遅くなります。 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 2

ちょうど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