Python 是否有大 numbers/lists 的问题，或者我的代码有问题？

Question

我有以下代码：

def main(n):
    sequence = []
    while n not in sequence:
        sequence.append(n)

        if n % 2 == 0:
            i = n / 2
        else:
            i = (n * 3) + 1
        n = int(i)

    print("Sequence length: " + str(len(sequence)-1))

n = int(input("Number: "))
main(n)

它从用户那里获取一个整数，然后计算该数字的“3x+1”（或 'Collatz'）序列（有关详细信息，请参阅 http://www.ericr.nl/wondrous/index.html#part1）。然后显示序列的长度。

为了确保我的代码按预期工作，我将我的结果与 http://www.ericr.nl/wondrous/delrecs.html 上的 table 进行比较 'Delay' 列似乎是序列长度，并且 'N' 是输入的初始整数。我的代码为所有 'N' 值（我随机测试过）给出了正确的长度，最大为 1,899148,184679 (#92)。但是，对于 'N' 的下一个值（2,081751,768559，#93），它给出的长度为“385”（而不是“1437”）... [=29 上的所有值也是如此=]（我已经测试过）比 table 上的要大 - 我的代码给出的答案比他们所做的要小得多。

Python 是否存在可能导致此行为的大数字问题，或者我的代码有问题？

我承认我不完全理解 'delay records'，或者确实不完全理解该网页上的大部分信息。但是，即使我假设 'delay record' 只是此方法生成的序列的长度是错误的，但我的代码会计算相同的值直到该特定数字为止似乎很奇怪...

我正在使用 Python 3.8.10 以防相关。

Answer 1

您需要使用 // 而不是 /
错误发生在 number:19981441939834942，这是序列中的第 85 个索引。

测试代码：

x = 19981441939834942
print(19981441939834942 // 2)
print(int(19981441939834942 / 2)) # your code to calculate it.

测试结果：

9990720969917471 #correct result
9990720969917472 #wrong result

固定码：

def main(n):
    sequence = []
    while n not in sequence:
        sequence.append(n)

        if n % 2 == 0:
            n = n // 2 # you use `/` then convert to int, which may cause wrong result when n is a huge number.
        else:
            n = (n * 3) + 1
        # n = int(i)
    print("Sequence length: " + str(len(sequence)-1))

n = 2081751768559
main(n)

结果：

Sequence length: 1437

Answer 2

您遇到浮点错误。 “但我用的是整数！”我听到你说，好吧 Python 正在这条线上做浮点数除法：

i = n / 2

看似无伤大雅，但改成整数除法就解决了问题：

i = n // 2

经过数百个值后，其中一个除法给您一个错误，该值比实际整数值小一些 epsilon，然后在您调用 int(n).

时向下舍入

编辑：在仔细检查我的最后一点以找到失败的值之后，我不太正确。实际发生的情况是，由于 Pythons BigInt 实现，整数除法始终准确，但浮点数除法并非如此，因为它仍然使用常规浮点数来提高速度。如果您的数字足够大，那么根本就没有足够的字节来准确存储数字，这将导致舍入错误。

有问题的号码是19981441939834942。使用整数除法得到 9990720969917471，而浮点除法得到 9990720969917472.0.

这在你使用的任何语言中都会是一个问题（除了大多数其他语言不允许你不小心对整数使用浮点除法），所以一定要使用整数除法！

Python 是否有大 numbers/lists 的问题，或者我的代码有问题？

Does Python have trouble with large numbers/lists, or is there something wrong with my code?

python

largenumber

collatz

测试代码：

测试结果：

固定码：

结果：