这是公认的最快的斐波纳契数列ruby算法

[Copy to clipboard] [ - ]

CODE:

fib = Hash.new{|h,n| n<2 ? h[n]=n : h[n]=h[n-1]+h[n-2]}

直接算fib[5000]给出的是“stack level too deep”
可是先算fib[4000]再算一遍fib[5000]就给出结果了
谁能解释一下

好奇妙的用法

错误原因应该是嵌套太深了，

fib = Hash.new{|h,n| n<2 ? h[n]=n : h[n]=h[n-1]+h[n-2]}

puts fib.size >> 0 说明刚定义的时候fib里面没有任何值

fib[4000]

puts fib.size >> 4001 这时候，fib这个hash里面已经有4001个值了（包括 fib[0]）

fib[5000]

这时不用递归到 0 ，只要递归到 4000 就行，所以没有出错。
以上只是我的个人理解，真要分析清楚估计要去看 ruby 的源码了。

ps 刚才试出4396是极限

递归总是很吓人的。不递归也挺快的。

[Copy to clipboard] [ - ]

CODE:

def Fri(x)
f1 = f2 = 1
1.upto(x-1) {f2 = f2 + f1 = f2 - f1}
puts f2
end
Fri(5000)

再来看看这个代码

[Copy to clipboard] [ - ]

CODE:

  $fib = Hash.new{|h,n| n<2 ? h[n]=n : h[n]=h[n-1]+h[n-2]}

  def fib(n)
    (1/5 ** 0.5) * (((1 + 5 ** 0.5)/2) ** n - ((1 - 5 ** 0.5)/2) ** n)
  end

最大支持到 1474， fib(1475) 就会出现 Infinity
而且 fib(71).to_i == $fib[71]

当算到72的时候

fib(72).to_i = 498454011879265
$fib[72] = 498454011879264

显然在乘方运算出现了误差。
欢迎提出意见～

这是程序是在那些编辑器上输入的的，看上去挺好的