Skip to content

Instantly share code, notes, and snippets.

@robot-dreams

robot-dreams/fib.hs

Last active January 17, 2017 00:43
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save robot-dreams/0069dd7558f898028659d41be9689185 to your computer and use it in GitHub Desktop.
Save robot-dreams/0069dd7558f898028659d41be9689185 to your computer and use it in GitHub Desktop.
Download ZIP
Fibonacci in logarithmic time
Raw
fib.hs
fib :: Int -> Integer
fib n =
let fibTriplet k
| k <= 0 = (0, 0, 1)
| k == 1 = (0, 1, 1)
| even k = let (a, b, c) = fibTriplet (k `div` 2)
in (a^2 + b^2, b * (a + c), b^2 + c^2)
| odd k = let (a, b, c) = fibTriplet (k - 1)
in (b, c, b + c)
snd3 (_, y, _) = y
in snd3 $ fibTriplet n
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment