Fibonacci in O(log N)

I found this beautiful algorithm while going through suggested exercise in SICP . For more detailed discussion see http://vikrant.infogami.com/blog/efficientfib

    fibiter a b p q count
| count == 0        = b
| odd count         = fibiter (b*q + a*q + a*p) (b*p + a*q) p q (count -1)
| otherwise         = fibiter a b p1 q1 (count `div` 2)
where
p1 = p*p + q*q
q1 = q*q + 2*p*qefficientfib = fibiter 1 0 0 1

efficientfib = fibiter 1 0 0 1
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s