# 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 Commented Oct 11, 2012 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. Commented Oct 11, 2012 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? Commented Oct 12, 2012 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). Commented Oct 20, 2012 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. Commented Oct 12, 2012 at 1:53
• That's correct, the OP's recurrence is underdefined. Commented Oct 12, 2012 at 2:21
• Note that matrix powering can be speeded up dramatically by exponentiation by squaring. Commented Mar 11, 2013 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$? Commented Mar 11, 2013 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]$. Commented Mar 11, 2013 at 10:53