项目Euler#25:持续溢出错误(结果很大) - 是否与计算斐波那契数量有关？

Question

我正在努力解决Project Euler问题25:

Fibonacci序列中包含1000位数的第一项是什么？

我的代码片段适用于较小的数字,但是当我尝试1000位数时,我得到错误:

OverflowError: (34, 'Result too large')

我在想它可能是我如何计算斐波纳契数,但我尝试了几种不同的方法,但我得到了同样的错误.

这是我的代码:

'''
 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类型计算.

因此,由于您使用的是近似值,使用浮点计算,最终会得到该问题.

相反,尝试以正常方式计算Fibonacci序列,一次计算一个(序列的)数,直到达到1000位.

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

通过"正常方式"我的意思是:

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

请注意,给出上述公式的"明显"方法对于这个特定问题是错误的,所以我会发布错误方法的代码,以确保您不会浪费时间:

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位或更多位的Fibonacci数是序列中的第4782位数(除非我计算错误),因此递归方法中对fib函数的调用次数将是这个数:

1322674645678488041058897524122997677251644370815418243017081997189365809170617080397240798694660940801306561333081985620826547131665853835988797427277436460008943552826302292637818371178869541946923675172160637882073812751617637975578859252434733232523159781720738111111789465039097802080315208597093485915332193691618926042255999185137115272769380924184682248184802491822233335279409301171526953109189313629293841597087510083986945111011402314286581478579689377521790151499066261906574161869200410684653808796432685809284286820053164879192557959922333112075826828349513158137604336674826721837135875890203904247933489561158950800113876836884059588285713810502973052057892127879455668391150708346800909439629659013173202984026200937561704281672042219641720514989818775239313026728787980474579564685426847905299010548673623281580547481750413205269166454195584292461766536845931986460985315260676689935535552432994592033224633385680958613360375475217820675316245314150525244440638913595353267694721961

这仅仅是第4782个数字.实际值是所有斐波纳契数从1到4782的所有值的总和.这是不可能完成的.

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