O(log n) Fibonacci

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

O(log n) Fibonacci

Post by snar »

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

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar »

Q-Matrix. GIYF.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post 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.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder »

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

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro »

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

Post Reply

Return to “Algorithms”