python - 改进在 Python 3 中查找第 n 个斐波那契数的 Binet 公式的实现
问题描述
我试图在 Python 3 中实现 Binet 的公式来查找第 n 个斐波那契数。
def nth_fib(n):
# this function returns fibonacci number of
# the given term by using Binet's Formula
sq5 = 5 ** 0.5
phi = (sq5 + 1) / 2
fib = (phi ** n) - (-phi ** -n)
fib //= sq5
return int(fib)
这个实现的问题:
它可以处理的最大值是 1474。传递大于 1474 的值会引发以下异常。
OverflowError: (34, 'Numerical result out of range')
如何改进此解决方案以处理从0 到 10^14的输入?
参考:
解决方案
发生这种情况是因为任意大的幂运算仅适用于整数,而整数在 Python 中是 bignums。浮点数将失败。例如:
In [41]: phi
Out[41]: 1.618033988749895
In [42]: 5 ** 1500
Out[42]: 28510609648967058593679017274152865451280965073663823693385003532994042703726535281750010939152320351504192537189883337948877940498568886988842742507258196646578577135043859507339978111500571726845535306970880115202339030933389586900213992268035185770649319797269196725831118636035211367342502592161612681404558896878205505259742673921998666848316296574456143285153407461693074529608060405705703190247031916733545429301523565202628619442784043773875799299799772062596279270685668750358350581239751392647377917727924073955752619811973924353072146897222054396284190793435454619462166959138549077025548151961129557730113226497053327025918024691450322204632795881761117317264715060152457060422911440809597657134113164654343933125576083446389585308532864118204843115878436344284086952443434298108182889069338971572783051504615283483170635029160778619107133456847839866260715887917144004772675646444499010890878045793828781976559446412621993167117009741097351499347086624666372905178820086046962818676294533224769602031134496655795373953878879547119140625
In [43]: phi ** 1500
---------------------------------------------------------------------------
OverflowError Traceback (most recent call last)
<ipython-input-43-38afd4fed496> in <module>()
----> 1 phi ** 1500
OverflowError: (34, 'Numerical result out of range')
解决方案是使用Decimal类,它可以处理任意精度的浮点运算,包括求幂:
In [47]: from decimal import *
In [48]: getcontext().power(Decimal(phi), Decimal(1500))
Out[48]: Decimal('3.030123816655090678595267922E+313')
考虑到这一点,重写的nth_fib
函数可能看起来像这样(我已经合并了一些数学并删除了整数除法以避免类型错误):
from decimal import *
def nth_fib(n):
# Tweak your Decimal context depending on your needs.
ctx = Context(prec=60, rounding=ROUND_HALF_EVEN)
sq5 = Decimal(5 ** 0.5)
phi = Decimal(sq5 + 1) / 2
fib = (ctx.power(phi, Decimal(n)) - ctx.power(-phi, -n)) / sq5
return int(fib)
print(nth_fib(5))
print(nth_fib(1500))
应该给出如下输出:
5
13551125668563783707293396130000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
如评论中所述,对浮点数的任何操作都会累积错误,其规模取决于执行的操作及其频率。
我希望这有帮助。干杯!
推荐阅读
- r - 每年每周过滤最大数据值的迭代;R
- typescript - 如何在 Typescript 中获取类的通用参数类型
- python - Pandas 在列名中添加“.1”后缀
- excel - 提交表单后,管理将文件从 Golang 服务器发送到 React 前端的最佳方法是什么?
- python - 即使代码运行良好,Codeforces 法官也会出错
- runtime-error - 错误不干净的工作树。首先提交或存储更改
- ansible - Openshift 3 安装问题
- java - 设置 CardLayout
- c++ - 从多个函数输出到文件
- ubuntu - Ubuntu'-bash:nano:找不到命令'