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 的代码在大数 (int) 乘法方面存在错误，或者我正在做一些绝对疯狂的事情，完整性检查!

谢谢!

编辑

我在在线 python 解释器中编写了第二个示例代码，特别是 2.xx 而不是 3.xx，但正如你们中的一些人所说，我确实在 3.x 中运行了代码。重做 3.xx 中的第二个操作并替换。不知道是否有人知道为什么代码有两个不同的值来表示应该相同的值。

编辑 - 2014 年 7 月 12 日

经过进一步检查后，我似乎遇到了一个因素不正确的情况(使用 Wolfram Alpha 进行检查)并且我已经切换了算法。稍后我将在 2.7 中使用 long 进行测试。

Answer 1

Python3 has changed what the division operator does .

在 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