Python中如何高效对超大偶整数除2且避免float溢出错误

最优解决方案 #

Python原生支持任意精度整数运算，完全不需要引入mpmath等第三方库，也不会触发float溢出问题，你只需要统一使用整数除法运算符// 替换原来的浮点除法/即可，这是当前性能最高的实现方式。
正确实现代码如下：

return n // 2 if (n % 2) == 0 else (3 * n + 1) // 2

性能优化建议 #

• 用位运算替换取模和除法，进一步提升运算速度：
  对于正整数而言，n & 1等价于n % 2判断奇偶，n >> 1等价于n // 2的运算结果，位运算的执行效率比算术运算更高，优化后代码：

  return n >> 1 if (n & 1) == 0 else (3 * n + 1) >> 1
  

• 你测试得到的//和>>运算性能低于mpf的结果属于反常情况，大概率是测试逻辑引入了额外开销，建议单独统计核心运算的耗时，排除无关代码的影响。
• 如果需要执行数百万次循环，切换到PyPy解释器运行可以获得数倍的性能提升，PyPy对循环和整数运算的优化远优于CPython。

原问题原因说明 #

你遇到的溢出报错是因为Python3中/运算符默认返回float类型，而float类型最多只能精确表示不超过2^53的整数，超过这个范围的整数转换为float时要么丢失精度，要么直接触发溢出错误。而//和位运算全程用Python原生大整数类型运算，不会涉及float转换，完全不存在溢出问题，运算效率也远高于第三方库的实现。

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