I have implemented a code that generate the infinite sequence given the base case and the coefficients of a linear recurrence relation.
import Data.List
linearRecurrence coef base | n /= (length base) = []
| otherwise = base ++ map (sum . (zipWith (*) coef)) (map (take n) (tails a))
where a = linearRecurrence coef base
n = (length coef)
Here is a implementation of Fibonacci numbers. fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))
It's easy to see that
linearRecurrence [1,1] [0,1] = fibs
However the time to calculate fibs!!2000
is 0.001s, and around 1s for (linearRecurrence [1,1] [0,1])!!2000
. Where does the huge difference in speed come from? I have made some of the functions strict. For example, (sum . (zipWith (*) coef))
is replaced by (id $! (sum . (zipWith (*) coef)))
, and it did not help.
You are computing linearRecurrence coef base
repeatedly. Make use of sharing, as in:
linearRecurrence coef base | n /= (length base) = []
| otherwise = a
where a = base ++ map (sum . (zipWith (*) coef)) (map (take n) (tails a))
n = (length coef)
Note the sharing of a
.
Now you get:
*Main> :set +s
*Main> fibs!!2000
422469...
(0.02 secs, 2203424 bytes)
*Main> (linearRecurrence [1,1] [0,1])!!2000
422469...
(0.02 secs, 5879684 bytes)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With