Last active
December 31, 2015 20:39
-
-
Save allykzam/8041374 to your computer and use it in GitHub Desktop.
This code will find "the last 20 elements of the Fibonacci series backwards" Of course it will never actually work. Runs for about 5 seconds on my machine and then complains it's out of memory.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{- | |
- Fast doubling Fibonacci algorithm | |
- Copyright (c) 2011 Nayuki Minase | |
- | |
- http://nayuki.eigenstate.org/page/fast-fibonacci-algorithms | |
-} | |
-- fibonacci n = F(n) | |
fibonacci :: Integer -> Integer | |
fibonacci n | n >= 0 = a where (a, _) = fib n | |
-- Internal function: fib n = (F(n), F(n+1)) | |
fib :: Integer -> (Integer, Integer) | |
fib 0 = (0, 1) | |
fib n = | |
let (a, b) = fib (div n 2) | |
c = a * (2 * b - a) | |
d = b * b + a * a | |
in if mod n 2 == 0 | |
then (c, d) | |
else (d, c + d) | |
{- Should get farther with a faster algo -} | |
fibs = map fibonacci [1..] | |
lastN n xs = let m = length xs in drop (m-n) xs | |
end = lastN 20 fibs | |
result = reverse end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment