Page 1 of 1
O(log n) Fibonacci
Posted: Fri Jul 21, 2006 2:56 pm
by snar
Can anyone explain me O(log n) Fibonacci method?
--
Thanks
--
Posted: Fri Jul 21, 2006 3:11 pm
by sumankar
Q-Matrix. GIYF.
Posted: Fri Jul 21, 2006 3:13 pm
by mf
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.
Posted: Mon Jul 31, 2006 7:29 am
by bugzpodder
the n-th fibonnacci number can be find by raising the golden ratio to the power of n and round it.
Posted: Mon Jul 31, 2006 7:49 pm
by Cosmin.ro
bugz you need infinite precision real numbers foe that ...