如果您确实想使用该算法,并且希望超越内置的
float
限制,那么是的,您需要不同的类型。
如果您只想获得近似答案而不是异常,那很简单;您可以直接使用无穷范围。但是,如果您还想消除舍入误差,则无法具有无限精度(这将花费无限时间/空间),因此您必须知道如何计算所需精度以用于输入范围。(我会把这留给读者作为练习。)
标准库类型
decimal.Decimal
可能是您所需的全部内容。它根据IEEE-854标准提供任意精度的定点或浮点十进制算术。虽然它不提供足够的数学函数而对许多情况不可用,但您只需要基本算术和
sqrt
,它就能够胜任。 对于大型数字,它也可能很慢,但是如果您只想在几个三位数上计算
fib
,则足够了。
当
Decimal
不足时,通常会使用一些第三方模块来包装行业标准的 C 库,例如 gmp/mpfr,比如
bigfloat。
以下是如何获得无限范围,但舍入误差大致与内置浮点数相同的方法:
>>> 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
但请注意,这两个答案都不是您在完美计算时得到的答案;您已经因为舍入误差而丢失了24位数字。(这些值不同的原因是
bigfloat
在二进制中进行舍入,而
decimal
则在十进制中进行舍入。)
为了解决这个问题,您需要更多的精度。所有库都提供一些改变精度的方法;
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