Calculating Fibonacci numbers

http://www.ics.uci.edu/~dan/class/161/notes/7/Fib.html

Divide-and-conquer:

    Fib3(n)
       i := 1
       j := 0
       k := 0
       h := 1
       while n > 0 do
          if n is odd then
             t := jh
             j := ih + jk + t
             i := ik + t
          t := h2
          h := 2kh + t
          k := k2 + t
          n := floor( n/2 )
       return j

    T(n) = Θ(log n)

Fib3 works by making use of the fact that
        _      _  n        _            _
       |  0  1  |         |  fn-2  fn-1  |
       |        |     =   |              |
       |_ 1  1 _|         |_ fn-1  fn   _|