Fibonacci numbers

FROM

time complexity : O(lgN)
idea

F2n-1 = Fn^2 + (Fn-1)^2F2n = (2*Fn-1 + Fn)*Fn 

If n is even then k = n/2:F(n) = [2*F(k-1) + F(k)]*F(k)If n is odd then k = (n + 1)/2F(n) = F(k)*F(k) + F(k-1)*F(k-1)