Python - 大整数精度丢失

Question

编辑

现在可以用了！！！感谢大家的建议！ //= 在这个函数中是从2.x版本迁移到3.x版本时需要的

我正在尝试在Python中快速分解非常大的数字。这个过程进行得还不错，但当我把得到的质数相乘时，结果和原始值之间有很大的差异。

代码：

import math

x = 4327198439888438284329493298321832193892183218382918932183128863216694329


def getPrimes(n):
    num = abs(n)
    factor = 2
    primes = []
    while num > 1:
        factor = getNext(num, factor)
        primes.append(factor)
        num /= factor
    if n < -1:
        primes[0] = -primes[0]
    return primes

def getNext(n, f):
    if n % 2 == 0:
        return 2
    for x in range(max(f, 3), int(math.sqrt(n) + 1), 2):
        if n % x == 0:
            return x
    return n

values = getPrimes(x)

orig = int(1);

print(values)
for y in values:
    orig *= int(y)

print("\n") 
print(x)
print("\n")
print(orig)
print("\n")
print(orig-x)

输出：

[17, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
3, 83, 20845357395553.0]


4327198439888438284329493298321832193892183218382918932183128863216694329


4327198439888438374354383059307859040070974971297410068584490149575917568


90024889760986026846178791752914491136401361286359223239

???

在把原始数字逐步除下去时，能够顺利找到其中一个质因数。这让我相信我在上面的分解中得到的因数是正确的。

>>> x /= 17
>>> x /= 20845357395553
>>> x /= (2**185)
>>> x /= 3
>>> x
83.0
>>> x /= 83
>>> x
1.0
>>>

总结

我觉得Python的代码在处理大数字（整数）乘法时可能有错误，或者我可能在做一些非常疯狂的事情，求大家帮我检查一下！

谢谢！

编辑

我在一个在线的Python解释器中做了第二个示例代码，特别是使用了2.xx版本，而不是3.xx版本，但我确实在上面提到的3.x版本中运行了代码。有些人提到过这个问题。我在3.xx版本中重新做了第二个操作并进行了替换。不知道有没有人能解释一下为什么代码会有两个不同的值，而它们应该是相同的。

编辑 - 2014年7月12日

经过进一步检查，我发现我的因数有误（我用Wolfram Alpha检查过），所以我换了算法。我稍后会在2.7版本中测试长整型。

Answer 1

Python3改变了除法运算符的功能.

在Python 2中：

>>> 3 / 2
1

在Python 3中：

>>> 3 / 2
1.5
>>> 3 // 2
1

因此，你的 getprimes() 函数应该包含以下代码：

while num > 1:
    factor = getNext(num, factor)
    primes.append(factor)
    num //= factor