O(log n) Fibonacci

snar · Post by **snar** » Fri Jul 21, 2006 2:56 pm

Can anyone explain me O(log n) Fibonacci method?
--
Thanks
--

sumankar · Post by **sumankar** » Fri Jul 21, 2006 3:11 pm

Q-Matrix. GIYF.

mf · Post by mf » Fri Jul 21, 2006 3:13 pm

n-th power of matrix {{1,1},{1,0}} (or {{0,1},{1,1}}) contains n-th fibonacci number on its side diagonal (can be easily proved by induction.)
You can compute n-th power in O(log n) time.

bugzpodder · Post by **bugzpodder** » Mon Jul 31, 2006 7:29 am

the n-th fibonnacci number can be find by raising the golden ratio to the power of n and round it.

Cosmin.ro · Post by **Cosmin.ro** » Mon Jul 31, 2006 7:49 pm

bugz you need infinite precision real numbers foe that ...