python3中求n个Fibonacci数的Binet公式的改进实现

Question

我尝试在Python3中实现Binet的计算第n个Fibonacci数的公式

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中是bignum。浮点数将失败。例如：

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

如评论中所述，浮点数上的任何操作都会累积错误，其规模取决于所执行的操作及其频率

我希望这有帮助。干杯