blob: 29103b2889babab9fbab7ee6ac2aeaa50ff16f0b (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
module Template
( fib
) where
import Data.Bits
import Data.List
-- https://wiki.haskell.org/The_Fibonacci_sequence
fib :: Int -> Integer
fib n =
snd
. foldl_ fib_ (1, 0)
. dropWhile not
$ [ testBit n k | k <- let s = bitSize 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' -- '
|