G'day all.
Quoting Vladimir Portnykh <[EMAIL PROTECTED]>:
> I wrote my own Fibonacci numbers generator:
>
> fib :: Int -> [Int]
> fib 0 = [0,0]
> fib 1 = [1,0]
> fib n = [sum prevFib, head prevFib] where a = fib (n - 1)
>
> To get the k-th number you do the following:
>
> result = head (fib k)
[...]
> Can we do better?
Sure we can. We can use a more efficient algorithm:
fib :: Integer -> Integer
fib k
| k < 0 = error "fib"
| otherwise = fst (fib' k)
fib' :: Integer -> (Integer,Integer)
fib' 0 = (0,1)
fib' k
| k `mod` 2 == 0
= let (a,b) = fib' (k `div` 2 - 1)
c = a + b
c2 = c*c
in (c2 - a*a, c2 + b*b)
| otherwise
= let (a,b) = fib' ((k-1) `div` 2)
c = a+b
a2 = a*a
in (b*b + a2, c*c - a2)
Cheers,
Andrew Bromage
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
