You are viewing a single comment's thread. Return to all comments →
You can get logarithmic time.
fib :: Int -> Integer fib n = snd . foldl_ fib_ (1, 0) . dropWhile not $ [testBit n k | k <- let s = finiteBitSize n in [s-1,s-2..0]] where fib_ (f, g) p | p = (f * (f + 2*g), ss) | otherwise = (ss, g * (2*f - g)) where ss = f*f + g*g foldl_ = foldl' -- '
Seems like cookies are disabled on this browser, please enable them to open this website
Fibonacci
You are viewing a single comment's thread. Return to all comments →
You can get logarithmic time.