大数值计算异常：Collatz猜想Python实现为何出现偏差？

问题描述 #

我在repl.it上编写了一个演示Collatz猜想的Python程序，逻辑是对输入的正整数递归执行：偶数则除以2，奇数则3n+1，最终应收敛到1。但输入超大数值（如6666666666666666666666666）时，计算结果出现异常：

Give me a positive integer: 6666666666666666666666666
Thank you.
Now loading:
1: 6666666666666666666666666
2: 3333333333333333277409280
...

预期第二步结果应为3333333333333333333333333，但实际结果明显不符；输入1000000000000000000000000时，第二步得到499999999999999991611392，同样偏离预期。

问题根源 #

这个异常的核心原因是Python中浮点数的精度限制：

• 在你的代码中，处理偶数时使用了n = n / 2，Python 3里/运算符会返回浮点数（float类型），而标准64位双精度浮点数只有53位有效精度，只能精确表示十进制下约16位以内的整数。
• 当输入的整数远大于这个范围（比如你输入的25位整数），转成浮点数时会丢失部分精度，存储的是原数的近似值，后续的除法自然无法得到精确结果。

举个直观的例子：6666666666666666666666666是一个远超53位精度的整数，转成浮点数后已经被近似为一个最接近的可表示值，此时再除以2，结果自然和真实的整数除法结果不符。

解决方案 #

将代码中的浮点数除法替换为整数除法：
把这一行：

n = n / 2

修改为：

n = n // 2

//是Python的整数除法运算符，它会保持结果的整数类型。Python支持任意精度的整数，无论输入的数值多大，只要在内存允许范围内，都能进行精确计算。修改后，你输入的超大整数就能得到正确的第二步结果了。

验证 #

修改代码后，输入6666666666666666666666666，第二步会输出：

2: 3333333333333333333333333

完全符合预期。

内容的提问来源于stack exchange，提问作者Luismi98