class Integer
  FibonacciCache = Hash.new do |hash, key|
    if hash.has_key?(key - 1) and hash.has_key?(key - 2)
      hash[key] = hash[key - 1] + hash[key - 2]
    elsif hash.has_key?(key + 1) and hash.has_key?(key + 2)
      hash[key] = hash[key + 2] - hash[key + 1]
    else
      subkey = key.div(2)
      case key.modulo(4)
        when 1
          hash[key] = (2*hash[subkey] + hash[subkey - 1])*(2*hash[subkey] - hash[subkey - 1]) + 2
        when 3
          hash[key] = (2*hash[subkey] + hash[subkey - 1])*(2*hash[subkey] - hash[subkey - 1]) - 2
        else
          hash[key] = hash[subkey] * (hash[subkey] + 2*hash[subkey - 1])
      end
    end
  end
  FibonacciCache[0] = 0
  FibonacciCache[1] = 1

  def fib
    return FibonacciCache[self]
  end

  def fib_uncached
    return FibonacciCache.dup[self]
  end
end

start_time = Time.now
1_000_000.fib
#fibs = (5..10).map { |i| i.fib }
#fibs = (1..100000).map { |i| i.fib }
#puts fibs.size
#puts fibs.last
p Time.now - start_time

puts "Doesn't work !" unless (1..10).map { |i| i.fib } == [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]


#-----------------------------------------------------------------------


# From: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/37727
# Author: Shin-ichiro HARA


  class QR3
    attr_reader :a, :b

    def inspect
      "{#{@a},#{@b}}"
    end
    alias to_s inspect

    def initialize(a, b)
      @a, @b = a, b
    end

    def *(r)
      u = (@a + @b)*(r.a + r.b)
      v = (@a - @b)*(r.a - r.b)
      QR3.new((u + v)>>1, @b*r.b + ((u - v)>>1))
    end

    def **(n)
      if n == 0
        QR3.new(1, 0)
      elsif n > 0
        z = x = self
        n -= 1
        while (z*= x if n[0].nonzero?; (n >>= 1).nonzero?)
          x *= x
        end
        z
      end
    end
  end

  def fib_qr3(n)
    (QR3.new(0, 1)**n).b
  end

n = 1000

start_time = Time.now
fib_qr3(n)
p Time.now - start_time