Skip to content

Instantly share code, notes, and snippets.

@gergoerdi

gergoerdi/Fib.hs

Created Jun 22, 2016
Embed
What would you like to do?
fib' :: (Integer, Integer) -> (Integer, Integer) -> Integer -> Integer
fib' (p, q) (x0, x1) n = go n (p, q) (x0, x1)
where
go 0 (p, q) (x0, x1) = x0
go n (p, q) (x0, x1) = if odd then go (n-1) (p, q) $! step (p, q) (x0, x1)
else go n' (p', q') (x0, x1)
where
(n', b) = n `divMod` 2
odd = not (b == 0)
p' = p * p + q * q
q' = 2 * p * q + q * q
step (p, q) (x0, x1) = let x0' = p * x0 + q * x1
x1' = q * x0 + (p+q) * x1
in x0' `seq` x1' `seq` (x0', x1')
fib n | n >= 0 = fib' (0, 1) (0, 1) n
| otherwise = fib' (0, -1) (1, 0) (negate n + 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.