Fast fibonacchi method

fibo.rb

def fib(n)
  _fib(n).first
end

def _fib(n)
  if n == 0
    [0, 1]
  else
    a, b = _fib(n / 2)
    c = a * (2 * b - a)
    d = b * b + a * a
    (n % 2 == 0) ? [c, d] : [d, c + d]
  end
end

puts fib(100)

#
# f(1) = f(0) + 1                          : 1
# f(2) = f(1) + f(0) = f(0) + f(0) + 1     : 1
# f(3) = f(2) + f(1) = 2*f(1) + f(0)       : 2
# f(4) = f(3) + f(2) = 2*f(2) + f(1)       : 3
# f(5) = 2*f(3) + f(2)
=begin
# Fast doubling Fibonacci algorithm
# Copyright (c) 2011 Nayuki Minase


# Returns F(n)
def fibonacci(n):
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    return _fib(n)[0]


# Returns a tuple (F(n), F(n+1))
def _fib(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n / 2)
        c = a * (2 * b - a)
        d = b * b + a * a
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)
=end