Python 生成斐波那契数时溢出错误“数值结果超出范围”
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12666600/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
OverflowError 'Numerical result out of range' when generating fibonacci numbers
提问by fergusdawson
Possible Duplicate:
Handling very large numbers in Python
可能的重复：
在 Python 中处理非常大的数字
I have a python function to generate fibonacci numbers:
我有一个 python 函数来生成斐波那契数列：
def fib(n):
return ((1+math.sqrt(5))**n - (1-math.sqrt(5))**n)/(2**n*math.sqrt(5))
I can feed the fib function numbers up to 700, where it starts to
我可以提供高达 700 的 fib 函数数，它开始
OverflowError: (34, 'Numerical result out of range')
Do I need to use a special type like long to get around this?
我是否需要使用像 long 这样的特殊类型来解决这个问题？
采纳答案by Michael Anderson
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.
问题是您使用双打来计算值并且双打溢出。双打只能给出大约第 85 个斐波那契数的精确解。
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.
如果您想要快速准确的计算，最好使用基于更好递归关系的算法，并使用 python bignum 整数。
In particular you can use:
特别是您可以使用：
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 ]
Both of these result in algorithms that require O(log(N))calculations rather than O(N).
这两者都会导致算法需要O(log(N))计算而不是O(N)。
Here's a complete solution in pseudo-code
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:
如果您确实想使用双精度数和显式公式执行计算，则可以调整公式以提供更快的结果，直到大约第 1500 次斐波那契数时才溢出，并保持与您的版本相同的精度。IIRC它是：
def fib(n):
return round( ((1+math.sqrt(5))/2)**n / math.sqrt(5) )
回答by John La Rooy
It's easy to isolate the error
很容易隔离错误
>>> (1+math.sqrt(5))**700
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OverflowError: (34, 'Numerical result out of range')
This method won't work well as floating point numbers don't have enough precision
由于浮点数没有足够的精度，此方法将无法正常工作
for example, here
例如，这里
>>> (1+math.sqrt(5))**600
1.024664165563927e+306
you are working with only the first 15 or so digits. The remaining 291 will be treated as zeros when you do any arithmetic
您只使用前 15 位左右的数字。当您进行任何算术运算时，剩余的 291 将被视为零
See wikipediafor more information about accuracy problems with floating point numbers
回答by arshajii
You can always try this approach:
您可以随时尝试这种方法：
def fib(n, memo={0:0, 1:1}):
if n not in memo:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
print fib(800)
Output:
输出：
69283081864224717136290077681328518273399124385204820718966040597691435587278383112277161967532530675374170857404743017623467220361778016172106855838975759985190398725
69283081864224717136290077681328518273399124385204820718966040597691435587278383112277161967532530675374170857404743017623467220361778016172106855838975759985190398725
回答by abarnert
If you actually want to use that algorithm, and you want to work beyond the limits of the built-in float, then yes, you need a different type.
如果您确实想要使用该算法，并且想要超越内置 的限制float，那么是的，您需要不同的类型。
If all you want is to get an approximate answer instead of an exception, that's easy; you can get infinite range out of the box. But if you also want to eliminate the rounding errors, you can't have infinite precision (that would take infinite time/space), so you have to know how to work out the precision needed for your range of inputs. (I'll leave that as an exercise for the reader.)
如果你只想得到一个近似的答案而不是一个例外，那很容易；您可以开箱即用地获得无限范围。但是，如果您还想消除舍入误差，则不能拥有无限精度（这将占用无限时间/空间），因此您必须知道如何计算输入范围所需的精度。（我将把它留给读者作为练习。）
The standard library type decimal.Decimalmay be all you need. It provides arbitrary-precision fixed- or floating-point decimal arithmetic according to the IEEE-854 standard. There are many cases for which it's unusable because it doesn't provide enough mathematical functions, but you only need basic arithmetic and sqrt, which are just fine. It can also be slow for huge numbers, but if you just want to calculate fibon a few three-digit numbers it's more than sufficient.
标准库类型decimal.Decimal可能就是您所需要的。它根据 IEEE-854 标准提供任意精度的定点或浮点十进制算术。在很多情况下它不可用，因为它没有提供足够的数学函数，但您只需要基本的算术和sqrt，就可以了。对于巨大的数字，它也可能很慢，但如果您只想计算fib几个三位数，那就足够了。
When Decimalis insufficient, there are a number of third-party modules, usually wrapping industry-standard C libraries like gmp/mpfr, such as bigfloat.
当Decimal不足时，有许多的第三方模块，通常包装业界标准C库等GMP / MPFR，如bigfloat。
Here's how to get infinite range, but with rounding errors on roughly the same scale as the built-in float:
以下是如何获得无限范围，但舍入误差与内置浮点数大致相同：
>>> s5 = decimal.Decimal(5).sqrt()
>>> def fib(n):
... return ((1+s5)**n - (1-s5)**n)/(2**n*s5)
>>> fib(800)
Decimal('6.928308186422471713629008226E+166')
>>> int(fib(800))
69283081864224717136290082260000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L
>>> s5 = bigfloat.sqrt(5)
>>> def fib(n):
... return ((1+s5)**n - (1-s5)**n)/(2**n*s5)
>>> fib(800)
BigFloat.exact('6.9283081864226567e+166', precision=53)
>>> int(fib(800))
69283081864226566841137772774650010139572747244991592044952506898599601083170460360533811597710072779197410943266632999194601974766803264653830633103719677469311107072L
But notice that neither of these are actually the answer you'd get if you did the math perfectly; you've lost 24 digits to rounding errors. (The reason the values are different is that bigfloatis rounding in base 2, decimalin base 10.)
但是请注意，如果您完美地进行数学运算，这些实际上都不是您得到的答案；你已经因为舍入错误而丢失了 24 位数字。（值不同的原因bigfloat是在基数 2 中舍入，decimal以 10 为基数。）
To fix that, you need more precision. All libraries provide some way to change the precision; bigfloathas more convenient options than most, but none are too onerous:
要解决这个问题，您需要更高的精度。所有的库都提供了一些改变精度的方法；bigfloat有比大多数更方便的选择，但没有一个太繁重：
>>> decimal.getcontext().prec = 300
>>> s5 = decimal.Decimal(5).sqrt()
>>> def fib(n):
... return ((1+s5)**n - (1-s5)**n)/(2**n*s5)
>>> fib(800)
69283081864224717136290077681328518273399124385204820718966040597691435587278383112277161967532530675374170857404743017623467220361778016172106855838975759985190398725.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000048
>>> def fibp(n, p):
... with bigfloat.precision(p):
... s5 = bigfloat.sqrt(5)
... return ((1+s5)**n - (1-s5)**n)/(2**n*s5)
>>> fibp(800, 125)
BigFloat.exact('6.92830818642247171362900776814484912138e+166', precision=125)
>>> int(fibp(800, 125))
69283081864224717136290077681448491213794574774712670552070914552025662674717073354503451578576268674564384721027806323979200718479461097490537109958812524476157132800L
