patternMinor
Optimize a linear recurrence
Viewed 0 times
linearrecurrenceoptimize
Problem
$$\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?
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?
Solution
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.
Context
StackExchange Computer Science Q#5018, answer score: 7
Revisions (0)
No revisions yet.