对 python 中的长数字使用数学模块的 sqrt 函数
Using the sqrt function of math module for long numbers in python
我在 python 中处理 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*x(201 位)大于 n(200 位)。这里发生了什么?有什么概念我在这里弄错了吗?我还能如何找到非常大的数的根?
math.sqrt
returns 一个 IEEE-754 64 位结果,大约是 17 位数字。还有其他库可以处理高精度值。除了上面提到的 decimal
和 mpmath
库之外,我还维护 gmpy2
库 (https://code.google.com/p/gmpy/).
>>> import gmpy2
>>> n=gmpy2.mpz(99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999982920000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000726067)
>>> gmpy2.get_context().precision=2048
>>> x=gmpy2.sqrt(n)
>>> x*x
mpfr('99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999982920000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000726067.0',2048)
>>>
gmpy2
库还可以 return 整数平方根 (isqrt
) 或快速检查整数是否为精确平方 (is_square
)。
这是我不久前写的一个使用 Hero 方法的整数平方根程序。对于初始近似值,它使用输入值位长度一半的数字,因此它开始收敛得非常快。但是,我没有对它进行计时,看看它在 Python 中是否比仅使用更简单的初始近似值更快。 :)
#! /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()
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
我在 python 中处理 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*x(201 位)大于 n(200 位)。这里发生了什么?有什么概念我在这里弄错了吗?我还能如何找到非常大的数的根?
math.sqrt
returns 一个 IEEE-754 64 位结果,大约是 17 位数字。还有其他库可以处理高精度值。除了上面提到的 decimal
和 mpmath
库之外,我还维护 gmpy2
库 (https://code.google.com/p/gmpy/).
>>> import gmpy2
>>> n=gmpy2.mpz(99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999982920000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000726067)
>>> gmpy2.get_context().precision=2048
>>> x=gmpy2.sqrt(n)
>>> x*x
mpfr('99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999982920000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000726067.0',2048)
>>>
gmpy2
库还可以 return 整数平方根 (isqrt
) 或快速检查整数是否为精确平方 (is_square
)。
这是我不久前写的一个使用 Hero 方法的整数平方根程序。对于初始近似值,它使用输入值位长度一半的数字,因此它开始收敛得非常快。但是,我没有对它进行计时,看看它在 Python 中是否比仅使用更简单的初始近似值更快。 :)
#! /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()
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