python - 欧拉计划 #25 : Keep getting Overflow error (result to large) - is it to do with calculating fibonacci number?

Question

我正在解决 Project Euler 问题 25:

What is the first term in the Fibonacci sequence to contain 1000 digits?

我的代码适用于较小的数字，但是当我尝试 1000 位时，出现错误:

OverflowError: (34, '结果太大')

我想这可能与我如何计算斐波那契数有关，但我尝试了几种不同的方法，但我得到了同样的错误。

这是我的代码:

'''
 What is the first term in the Fibonacci sequence to contain 1000 digits
'''

def fibonacci(n):
    phi = (1 + pow(5, 0.5))/2           #Golden Ratio
    return int((pow(phi, n) - pow(-phi, -n))/pow(5, 0.5))   #Formula: http://bit.ly/qDumIg


n = 0
while len(str(fibonacci(n))) < 1000:
    n += 1
print n

你知道这个问题的原因是什么吗？我该如何修改我的代码来避免这个问题？

提前致谢。

Answer 1

这里的问题是只有 Python 中的整数具有无限长度，浮点值仍然使用具有最大精度的普通 IEEE 类型计算。

因此，由于您使用的是近似值，使用浮点计算，您最终会遇到这个问题。

相反，请尝试以正常方式计算斐波那契数列，一次计算一个(数列的)数字，直到达到 1000 位。

即。计算 1, 1, 2, 3, 5, 8, 13, 21, 34 等

“正常方式”是指:

         /  1                        , n < 3Fib(n) = |         \  Fib(n-2) + Fib(n-1)      , n >= 3

Note that the "obvious" approach given the above formulas is wrong for this particular problem, so I'll post the code for the wrong approach just to make sure you don't waste time on that:

def fib(n):
    if n <= 3:
        return 1
    else:
        return fib(n-2) + fib(n-1)

n = 1
while True:
    f = fib(n)
    if len(str(f)) >= 1000:
        print("#%d: %d" % (n, f))
        exit()
    n += 1

在我的机器上，上面的代码在第 30 个斐波那契数附近开始非常变慢，它仍然只有 6 位长。

我修改了上面的递归方法来输出每个数字对 fib 函数的调用次数，这里有一些值:

#1: 1
#10: 67
#20: 8361
#30: 1028457
#40: 126491971

我可以揭示第一个具有 1000 位或更多数字的斐波那契数是序列中的第 4782 个数字(除非我计算错误)，因此在递归方法中调用 fib 函数的次数将是这个数字:

1322674645678488041058897524122997677251644370815418243017081997189365809170617080397240798694660940801306561333081985620826547131665853835988797427277436460008943552826302292637818371178869541946923675172160637882073812751617637975578859252434733232523159781720738111111789465039097802080315208597093485915332193691618926042255999185137115272769380924184682248184802491822233335279409301171526953109189313629293841597087510083986945111011402314286581478579689377521790151499066261906574161869200410684653808796432685809284286820053164879192557959922333112075826828349513158137604336674826721837135875890203904247933489561158950800113876836884059588285713810502973052057892127879455668391150708346800909439629659013173202984026200937561704281672042219641720514989818775239313026728787980474579564685426847905299010548673623281580547481750413205269166454195584292461766536845931986460985315260676689935535552432994592033224633385680958613360375475217820675316245314150525244440638913595353267694721961

这只是 第 4782 个数字。实际值是从 1 到 4782 的所有斐波那契数的所有这些值的总和。这永远不可能完成。

事实上，如果我们给代码 1 年的运行时间(简化为 365 天)，并假设机器每秒可以调用 10.000.000.000 次，那么算法将达到第 83 个数字，仍然只有 18 位数字。