生成斐波那契数时的OverflowError'数值结果超出范围' [英] OverflowError 'Numerical result out of range' when generating fibonacci numbers

问题描述

可能重复:
在Python中处理非常大的数字

Possible Duplicate:
Handling very large numbers in Python

我有一个生成斐波那契数的python函数:

I have a python function to generate fibonacci numbers:

def fib(n):                                                                                                            
        return ((1+math.sqrt(5))**n - (1-math.sqrt(5))**n)/(2**n*math.sqrt(5))

我最多可以提供700个fib函数编号，而

I can feed the fib function numbers up to 700, where it starts to

OverflowError: (34, 'Numerical result out of range')

我是否需要使用long这样的特殊类型来解决此问题?

Do I need to use a special type like long to get around this?

推荐答案

问题是您正在使用double来计算值，并且double溢出了. 双打仅给出大约第85个斐波那契数的精确解.

The problem is that you're using doubles to calculate the value and the doubles are overflowing. Doubles give exact solutions only to about the 85th Fibonacci number.

如果您想快速准确地进行计算，最好使用基于更好的递归关系的算法以及python bignum整数.

If you want a fast and accurate calculation you're better off using an algorithm based on a better recurrence relationship, and using python bignum integers.

特别是您可以使用:

 fib(2*n) = fib(n)^2 + fib(n-1)^2
 fib(2*n-1) = fib(n)*(2*fib(n-1)+fib(n))

或等效的矩阵求幂公式(请使用丑陋的格式)

Or the equivalent matrix exponentiation formula (excuse the ugly formatting)

 [ F_n     F_{n-1} ]      [ 1   1 ] ^N 
 [                 ]  =   [       ]
 [ F_{n-1} F_{n-2} ]      [ 1   0 ]

这两种方法都导致算法需要进行O(log(N))而不是O(N)的计算.

Both of these result in algorithms that require O(log(N)) calculations rather than O(N).

这是一个完整的伪代码解决方案

如果您确实想使用双精度和显式公式来执行计算，则可以对公式进行调整，以给出更快的结果，直到大约第1500个斐波那契数时才溢出，并保持与您的版本相同的精度. IIRC是:

If you do want to perform your calculations using doubles and the explicit formulae, then the formulae can be tweaked to give something faster that doesn't overflow until about the 1500th fibonacci number, and remains the same accuracy as your version. IIRC it is:

def fib(n):                                                                                                            
    return round( ((1+math.sqrt(5))/2)**n / math.sqrt(5) )

这篇关于生成斐波那契数时的OverflowError'数值结果超出范围'的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！