Project Euler #25：不断出现溢出错误（结果过大）- 这与计算斐波那契数有关吗？

Question

我正在解决Project Euler的第25个问题：

斐波那契数列中第一个包含1000位数字的项是什么？

我的代码在处理较小的数字时运行良好，但当我尝试处理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找到 fib(n) 的代码：

def fib(n):
    a = 1
    b = 1
    for i in range(2, n):
        b = a + b
        a = b - a
    return b

这个方法在定义 F(1) 为 1 的情况下有效，就像在 Project Euler 25 中那样。

我这里不会给出问题的确切解决方案，但上面的代码可以进行调整，以便在达到一个特定值（10**999）之前，持续跟踪 n 的值。

Answer 2

其实，虽然上面提到的建议是避免使用浮点数，这个建议在解决Project Euler的问题时通常是对的，但在这个情况下是不正确的。斐波那契数可以通过公式 F_n = phi^n / sqrt(5) 来计算，所以第一个超过一千位数的斐波那契数可以表示为 10^999 < phi^n / sqrt(5)。我们对两边取以十为底的对数——记住，sqrt(5) 就是 5 的 1/2 次方——得到 999 < n log_10(phi) - 1/2 log_10(5)。然后解这个不等式可以得到 n 的值为 (999 + 1/2 log_10(5)) / log_10(phi) < n。这个不等式左边的计算结果是 4781.85927，所以最小的 n 值，使得斐波那契数有一千位数，是 4782。

Answer 3

这里的问题是，只有整数在Python中可以无限大，而浮点数还是用普通的IEEE类型计算，这种类型有最大精度限制。

所以，由于你使用的是近似值，进行浮点计算时，最终会遇到这个问题。

相反，试着用正常的方法计算斐波那契数列，也就是一个一个地计算，直到你得到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

我可以告诉你，第4782个斐波那契数是第一个有1000位数的数（除非我算错了），所以在递归方法中调用fib函数的次数就是这个数字：

1322674645678488041058897524122997677251644370815418243017081997189365809170617080397240798694660940801306561333081985620826547131665853835988797427277436460008943552826302292637818371178869541946923675172160637882073812751617637975578859252434733232523159781720738111111789465039097802080315208597093485915332193691618926042255999185137115272769380924184682248184802491822233335279409301171526953109189313629293841597087510083986945111011402314286581478579689377521790151499066261906574161869200410684653808796432685809284286820053164879192557959922333112075826828349513158137604336674826721837135875890203904247933489561158950800113876836884059588285713810502973052057892127879455668391150708346800909439629659013173202984026200937561704281672042219641720514989818775239313026728787980474579564685426847905299010548673623281580547481750413205269166454195584292461766536845931986460985315260676689935535552432994592033224633385680958613360375475217820675316245314150525244440638913595353267694721961

而这仅仅是第4782个数字的情况。实际的值是从1到4782的所有斐波那契数的调用次数总和。根本不可能完成这个计算。

事实上，如果我们给这段代码1年的运行时间（简化为365天），假设机器每秒可以进行10,000,000,000次调用，那么这个算法最多只能计算到第83个数字，而那个数字也只有18位数。