SICP Exercise 1.19.rb

# Fibonacci numbers in logarithmic time

def even?(n)
  n % 2 == 0
end

def fib(n)
  a = 1
  b = 0

  p = 0
  q = 1
  while n > 0
    if even?(n)
      op = p
      oq = q
      p = op**2 + oq**2
      q = oq * (2*op + oq)
      n /= 2
    else
      oa = a
      ob = b
      a = ob*q + oa*q + oa*p
      b = ob*p + oa*q
      n -= 1
    end
  end
  b
end