# Optimize a linear recurrence

\begin{align*} T[1] &= 1 \\ T[2] &= 2 \\ T[i] &= T[i-1] + T[i-3] + T[i-4] & \text{for $$i \gt 2$$} \\ \end{align*}

I have to calculate $T[N]$, but $N$ is too big ($\approx 10^9$), how can I optimize it?

• This formula doesn't even hold for small i If i = 3 then T[3] = T[2]+T[0]+T[-1] last two elements of sum are not defined. But when it comes to optimization you can cache intermediate results in associated data structure – Bartosz Przybylski Oct 11 '12 at 10:59
• On the other hand this formula looks like Fibonacci sequence. If we assume that T[0] = 1 and clearly T[i-2] = T[i-3] + T[i-4], then this might work. And as we all know there exists explicit formula for Fibonacci number. – Bartosz Przybylski Oct 11 '12 at 21:46
• See here, and please flesh out your question. Where does this recurrence come from? What have you tried? What does "too big" mean; for what purpose? What is the problem? – Raphael Oct 12 '12 at 7:27
• If you are interested in a closed form, here is a general comment how to tackle these kind of problems. Compute the first entries of the sequence. Then request the The encyclopedia of integer sequences, if your recurrence is that simple, you probably find a closed form. Otherwise you might simply solve you recurrence using a computer algebra software like Mathematica (the comment here is rsolve). – A.Schulz Oct 20 '12 at 7:44

As Bartek commented, you are missing a base case. You can compute large values of $T$ in several ways:

• Bartek's suggestion: Use an array to store all the entries computed so far.
• You can optimize the previous method, dramatically reducing the memory needed: store only the last $4$ entries of the array at each point in time.
• Use matrix powering. There are vectors $x,y$ and a matrix $A$ such that $T[N] = x'A^N y$. This approach is very similar to the previous one.
• Find an explicit solution to your recurrence $T[N] = \sum_{i=1}^4 c_i \lambda_i^n$ (there are other possible forms, but this is the most probable), and use this formula to calculate $T[N]$ directly.
• Just for my own edification, but wouldn't 4 base-cases need to be defined to have full rank when computing the closed form? That is if we took the characteristic polynomial, solved for x, and wanted to know the coefficients. – Nicholas Mancuso Oct 12 '12 at 1:53
• That's correct, the OP's recurrence is underdefined. – Yuval Filmus Oct 12 '12 at 2:21
• Note that matrix powering can be speeded up dramatically by exponentiation by squaring. – vonbrand Mar 11 '13 at 1:19

Imagine your solution now is Gn = Gn-1 + Gn-2 + Gn-3

The solution just changes to

[ Gn Gn-1 Gn-2 ] = [ Gn-1 Gn-2 Gn-3 ] [ 1 1 0 ]
[ 1 0 1 ]
[ 1 0 0 ]


Similarly

[ Gn-1 Gn-2 Gn-3 ] = [ Gn-2 Gn-3 Gn-4 ] [ 1 1 0 ]
[ 1 0 1 ]
[ 1 0 0 ]


So finally,

[ Gn Gn-1 Gn-2 ] = [ G3 G2 G1 ] [ 1 1 0 ] ^n-3
[ 1 0 1 ]
[ 1 0 0 ]


Calculating power of a matrix, $$M^n$$ can be done in O(log n).

For your case, the Matrix will be

[ Gn Gn-1 Gn-2 Gn-3] = [ Gn-1 Gn-2 Gn-3 Gn-4 ] [ 1 1 0 0]
[ 0 0 1 0]
[ 1 0 0 1]
[ 1 0 0 0]


There aren't enough initial values, but still. Define: $$A(z) = \sum_{n \ge 0} T[n] z^n$$ Properties of ordinary generating functions give for the recurrence: $$T[n + 4] = T[n + 3] + T[n + 1] + T[n]$$ $$\frac{A(z) - T[0] - T[1] z - T[2] z^2 - T[3] z^3}{z^4} = \frac{A(z) - T[0] - T[1] z - T[2] z^2}{z^3} + \frac{A(z) - T[0]}{z} + A(z)$$ This finally leads to form: $$A(z) = \frac{p(z)}{z^4 - z^3 - z - 1} = \frac{A_1}{1 - \phi z} + \frac{A_2}{1 - \overline{\phi} z} + \frac{B z + C}{1 + z^2}$$ Here $A_1$, $A_2$, $B$ and $C$ are constants depending on the initial $T$ values, and \begin{align*} \phi &= \frac{1 + \sqrt{5}}{2} \\ \overline{\phi} &= 1 - \phi = - \frac{\sqrt{5} - 1}{2} \end{align*} The first two are geometric series, the last one adds terms alternating between 0 and 1 to the solution. And as $\lvert \overline{\phi} \rvert \approx 0.618$ while $\phi \approx 1.618$, the first term dominates. The value at large $n$ is approximately $T[n] \approx A_1 \phi^n$.

• It's not clear that this closed form is easier to compute than the memoisation variant. In particular, how do you represent $\phi$? – Raphael Mar 11 '13 at 7:26
• @Raphael, you are probably right in that the matrix method with e.g. binary exponentiation is a better practical method of computing $T[n]$. – vonbrand Mar 11 '13 at 10:53