숫자 모듈의 sqrt 함수를 파이썬에서 긴 숫자로 사용하기

Question

저는 파이썬에서 200 자리 숫자로 작업했습니다. math.sqrt (n)를 사용하여 숫자의 제곱근을 찾을 때 잘못된 대답을 얻고 있습니다.

In[1]: n=9999999999999999999999999999999999999999999999999999999999999999999999 
     999999999999999999999999998292000000000000000000000000000000000000000000 
     0000000000000000000000000000000000000000000000000000726067 

In[2]: x=int(math.sqrt(n)) 

In[3]: x 
Out[1]: 10000000000000000159028911097599180468360808563945281389781327 
     557747838772170381060813469985856815104L 

In[4]: x*x 
Out[2]: 1000000000000000031805782219519836346574107361670094060730052612580 
     0264077231077619856175974095677538298443892851483731336069235827852 
     3336313169161345893842466001164011496325176947445331439002442530816L 

In[5]: math.sqrt(n) 
Out[3]: 1e+100 

x * x (201 자리)가 n (200 자리)보다 크기 때문에 x 값이 예상보다 커집니다. 여기서 무슨 일이 일어나고있는거야? 내가 여기서 틀리게되고있는 개념이 있니? 어떻게하면 매우 큰 숫자의 근원을 찾을 수 있습니까?

Answer 1

math.sqrt은 대략 17 자리의 IEEE-754 64 비트 결과를 반환합니다. 고정밀 값을 사용할 수있는 다른 라이브러리가 있습니다. 위에 언급 된 decimal 및 라이브러리 외에도 gmpy2 라이브러리 (https://code.google.com/p/gmpy/)를 유지합니다. 정수 정확한 광장 (is_square) 인 경우

>>> import gmpy2 
>>> n=gmpy2.mpz(99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999982920000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000726067) 
>>> gmpy2.get_context().precision=2048 
>>> x=gmpy2.sqrt(n) 
>>> x*x 
mpfr('99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999982920000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000726067.0',2048) 
>>> 

gmpy2 라이브러리는 또한 반환 할 수 있습니다 정수 제곱근 (isqrt) 또는 빠르게 확인.

Answer 2

다음은 내가 작성한 영웅의 방법을 사용한 정수 제곱근 프로그램입니다. 초기 근사를 위해 입력 값의 비트 길이의 절반을 사용하므로 매우 빠르게 수렴을 시작합니다. 그러나 파이썬에서 더 빠른 초기 근사값을 사용하는 것보다 빠르는지보기 위해 시간을 정했습니다. :)

#! /usr/bin/env python 

''' Long integer square roots. Newton's method. 

    Written by PM 2Ring. Adapted from C to Python 2008.10.19 
''' 

import sys 

def root(m): 
    # Get initial approximation 
    n, a, k = m, 1, 0 
    while n > a: 
     n >>= 1 
     a <<= 1 
     k += 1 
     #print k, ':', n, a 

    # Go back one step & average 
    a = n + (a>>2) 
    #print a 

    # Apply Newton's method 
    while k: 
     a = (a + m // a) >> 1 
     k >>= 1 
     #print k, ':', a 
    return a 

def main(): 
    m = len(sys.argv) > 1 and int(sys.argv[1]) or 2*10L**100 
    print "The Square Root of", m 
    print root(m) 

if __name__ == '__main__': 
    main() 

Answer 3

는 the decimal module 사용 :

import decimal 
D = decimal.Decimal 
n = D(99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999982920000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000726067) 

with decimal.localcontext() as ctx: 
    ctx.prec = 300 
    x = n.sqrt() 
    print(x) 
    print(x*x) 
    print(n-x*x) 

는

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999145.99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999983754999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998612677 

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999982920000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000726067.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 

0E-100