Fast Fibonacci algorithm

Let me show you a fast recursive function in Ruby to compute Fibonacci. The basic definition is Fib(n) = Fib(n-1) + Fib (n-2). With a minor improvement you can aslo compute Fib(n) = 3 Fib(n-3) + 2 Fib(n-4)


fibonacci = Hash.new { |hash, index|
  hash[index] = 2 * hash[index-4] + 3 * hash[index-3]
}.update(0 => 0, 1 => 1, 2 => 1, 3 => 2)

Each number is the sum of its two predecessors: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... Now here is something less trivial and much faster:


l = ->(h, n) { (h[n+1] + h[n-1]) * h[n] }
fibonacci = Hash.new { |hash, index|
	m = index/2
	hash[index] = (index % 2 == 0) ? l.call(hash, m) : l.call(hash, m+1) - l.call(hash, m)
}.update(0 => 0, 1 => 1, 2 => 1, 3 => 2)

I wanted to create a fast function - in O(log n). The basic idea is to compute Fib(n) from only values around Fib(n/2). When n is pair Fib(n) = ( Fib(n/2+1) + Fib(n/2-1) ) * Fib(n/2)

Another good idea is keeping the results already computed. This is called memoization. The results are kept in a hash which is available at every level of the recursion.

The computation to get one value is very fast.

With big numbers, I only check the number of digits. For example Fib(604711) is a number with 126377 digits. Yes it works.


p fibonacci[604711].to_s.length # example, should equal 126377

I hope you enjoyed those few lines of code. It may take some time to get what the code does exactly.