改进Python 3中Binet公式的实现

Question

我尝试实现Binet的公式以在Python 3中找到第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之间的输入？

参考：

• Binet's Formula for the nth Fibonacci number

Answer 1

之所以会这样，是因为Python的默认指数运算符**适用于整数，尽管Python中的整数具有任意精度，但浮点数却没有。例如：

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 fib

print(nth_fib(5))
print(nth_fib(1500))

哪个输出应该像：
5.000000000000000582838266731
1.355112566856378370729339613E+313

我希望这会有所帮助。干杯！