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
