计算斐波纳契数列时Python 浮点数精度损失问题

一、问题根源使用比内公式计算的时候代码用 Python 浮点数float双精度 64 位计算比内公式在n100时phi**n和psi**n数值差异极大导致减法时有效位丢失最终结果出现误差。二、解决精度损失的三种方案方案1使用 Python 高精度小数decimal模块通过decimal模块手动控制精度避免浮点数舍入误差fromdecimalimportDecimal,getcontextdeffib_binet_precise(n,precision100):# 设置足够高的精度至少 n 的位数 20getcontext().precprecision sqrt5Decimal(5).sqrt()phi(Decimal(1)sqrt5)/Decimal(2)psi(Decimal(1)-sqrt5)/Decimal(2)res(phi**n-psi**n)/sqrt5# 结果一定是整数直接取整returnint(res)print(fib_binet_precise(100))# 输出354224848179261915075✅ 优点完全保留精度可算到很大的n如n1000❌ 缺点比浮点数稍慢但远快于递归方案2使用整数递推完全避免浮点数最推荐直接用迭代/递推计算全程整数运算无任何精度问题deffib_iter(n):ifn1:returnn a,b0,1for_inrange(2,n1):a,bb,abreturnbprint(fib_iter(100))# 输出354224848179261915075✅ 优点速度最快、无精度损失、代码极简❌ 缺点不是「比内公式」的直接实现方案3使用矩阵快速幂 / 快速倍增法适合超大 n如果要算n10^6级别用快速倍增法基于斐波那契恒等式时间复杂度O(log⁡n)O(\log n)O(logn)deffib_fast_doubling(n):ifn0:return(0,1)a,bfib_fast_doubling(n1)# n//2ca*(2*b-a)da*ab*bifn1:return(d,cd)else:return(c,d)deffib_fast(n):returnfib_fast_doubling(n)[0]print(fib_fast(100))# 输出354224848179261915075✅ 优点超大数据量下效率极高❌ 缺点理解成本稍高三、对比总结方案精度速度实现难度适用场景原始浮点数比内公式❌ 差快低仅适合小 nn70decimal高精度版✅ 满中中想保留「比内公式」形式且算大 n迭代递推✅ 满极快极低日常计算、面试首选快速倍增法✅ 满最快中超大 nn10^4四、最终推荐日常使用直接用迭代递推fib_iter代码最简单、无精度问题、速度最快。想保留比内公式形式用decimal模块提升精度设置足够大的precision。超大 n 场景用快速倍增法时间复杂度O(log⁡n)O(\log n)O(logn)算n10^6也瞬间出结果。更多内容 欢迎关注我的微信公众号: 半夏之夜的无情剑客