Solving Linear Recurrences with various methods, Including O(N logN logK) using FFT

Правка en1, от demoralizer, 2021-12-06 14:13:09

Linear Recurrence : Introduction

Fibonacci Sequence is one of the simplest examples of a linear recurrence: $$$F_x = F_{x-1} + F_{x-2}$$$, with $$$F_0 = 0, F_1 = 1$$$

Here is a more general example of a linear recurrence:

\begin{align} R_{x} = \sum_{i=1}^{n}{C_i \cdot R_{x — i}} \end{align}

where $$$C_i$$$ is constant and $$$R_x$$$ is the x-th term of the recurrence. Since $$$R_x$$$ depends on the previous $$$n$$$ terms of the recurrence, it is called a linear recurrence of order $$$n$$$. It is called a "Linear" Recurrence, since we do not have any terms of the type $$$R_x \cdot R_y$$$

Note: We need $$$n$$$ initial conitions for a linear recurrence of order $$$n$$$, for example, we have 2 initial conditions for the Fibonacci Sequence.

Iternary

In this blog we will learn about various methods of solving the following problem: Given a Linear Recurrence of order $$$N$$$, find the $$$K$$$-th term of the recurrence. There are various methods to do this:

  • $$$O(N \cdot K)$$$ using DP
  • $$$O(N^3 \cdot logK)$$$ using Matrix Exponentiation
  • $$$O(P(n) \cdot logK)$$$ using Characterstic Polynomials where P(n) is the time required for polynomial multiplication — which can be $$$O(N^2)$$$ naively or $$$O(N^{1.58})$$$ using Karatsuba Multiplication or $$$O(N logN)$$$ using Fast Fourier Transform.

DP Solution

The $$$O(N \cdot K)$$$ solution is pretty trivial. (Assume dp[0] .. dp[n-1] are stored correctly as initial conditions)

for(int i = n; i < k; i++){
    dp[i] = 0;
    for(int j = 0; j < n; j++){
        dp[i] += c[j] * dp[i - j];
    }
}

Matrix Exponentiation

Let's look at the problem from another angle. From the DP solution, it is clear that we need to keep track of the previous $$$n$$$ elements at all times, and it won't matter even if we "forget" other elements. So let's keep a column vector of the "current" $$$n$$$ consecutive elements. Since the recurrence relation is a Linear Relation, it is possible to have a linear transformation to get the next elements.

$$$ \begin{bmatrix} C_{n-1} \\ C_{n-2} \\ \vdots \\ C_0 \\ \end{bmatrix}

\underrightarrow{\text{A Linear Transformation}}

\begin{bmatrix} R_{n} \\ R_{n-1} \\ \vdots \\ R_1\\ \end{bmatrix} $$$

Finding this linear transformation is quite intuitive and it can be expressed as multiplication with a square matrix, so let's directly write the general result.

$$$ \begin{bmatrix} C_1 & C_2 & \cdots & C_{n-1} & C_n \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0\\ \end{bmatrix}

\begin{bmatrix} R_{i+(n-1)} \\ R_{i+(n-2)} \\ R_{i+(n-3)} \\ \vdots \\ R_{i+(0)}\\ \end{bmatrix}

\implies

\begin{bmatrix} R_{i+(n)} \\ R_{i+(n-1)} \\ R_{i+(n-2)} \\ \vdots \\ R_{i+(1)}\\ \end{bmatrix} $$$

Reader is advised to take a moment to manually mutliply the matrices and verify the above result for a better understanding.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский demoralizer 2021-12-07 12:35:32 28
en4 Английский demoralizer 2021-12-06 15:47:31 4
en3 Английский demoralizer 2021-12-06 15:39:31 3966 (published)
en2 Английский demoralizer 2021-12-06 14:41:55 1707
en1 Английский demoralizer 2021-12-06 14:13:09 3093 Initial revision (saved to drafts)