Compute Fibonacci numbers FAST! (idea)

I've tried all the methods above, but the method used by the GNU Multiple Precision (GMP) arithmetic library is at least five times faster than its nearest competitor in Ruby. Because GMP is optimized for speed and written in C, I assume the method works quickly in other languages as well.

To find the n^th Fibonacci number, use the following recursive definition :

• F₀ = 0
• F₁ = 1
• When n is an even number :
     F_n = F_{n / 2}(F_{n / 2} + 2 F_{(n−2) / 2})
• When n, modulo 4, is 1 :
     F_n = (2 F_{(n−1) / 2} + F_{(n−3) / 2})(2 F_{(n−1) / 2} − F_{(n−3) / 2}) + 2
• When n, modulo 4, is 3 :
     F_n = (2 F_{(n−1) / 2} + F_{(n−3) / 2})(2 F_{(n−1) / 2} − F_{(n−3) / 2}) − 2

Here's the Ruby code (using a hash table for memoization) :

class Integer
  FibonacciComputer = Hash.new do |fibonacci, n|
    if fibonacci.has_key?(n - 1) and fibonacci.has_key?(n - 2)
      fibonacci[n] = fibonacci[n - 1] + fibonacci[n - 2]
    elsif fibonacci.has_key?(n + 1) and fibonacci.has_key?(n + 2)
      fibonacci[n] = fibonacci[n + 2] - fibonacci[n + 1]
    else
      half_n = n.div(2)
      case n.modulo(4)
        when 1
          fibonacci[n] = (2*fibonacci[half_n] + fibonacci[half_n - 1])*(2*fibonacci[half_n] - fibonacci[half_n - 1]) + 2
        when 3
          fibonacci[n] = (2*fibonacci[half_n] + fibonacci[half_n - 1])*(2*fibonacci[half_n] - fibonacci[half_n - 1]) - 2
        else
          fibonacci[n] = fibonacci[half_n]*(fibonacci[half_n] + 2*fibonacci[half_n - 1])
      end
    end
  end
  FibonacciComputer[0] = 0
  FibonacciComputer[1] = 1
  FibonacciComputer.freeze
  
  def fib
    return FibonacciComputer.dup[self]
  end
end

puts "The 1,000th Fibonacci number is #{ 1_000.fib }."

Try it out at http://www.ruby.ch/interpreter/rubyinterpreter.shtml.