3 ms·
Computing Fibonacci numbers using only addition is very slow. Here's a much faster algorithm that uses multiplication: fibonacci n = fst (fib n) where
by cousin_it 9y ago
Computing Fibonacci numbers using only addition is very slow. Here's a much faster algorithm that uses multiplication:
fibonacci n = fst (fib n) where
fib 0 = (0, 1)
fib n = if even n then (c, d) else (d, c + d) where
(a, b) = fib (div n 2)
(c, d) = (a * (b * 2 - a), a * a + b * b)
- manx 9y agoInteresting, thank you for sharing. Though my main concern was more about introduction to recursion without an exponential algorithm.