Задача 6

Условие задачи

Докажите, что значение многочлена $f_n \left(x\right) = 1 + x + \ldots + x^n$ при $n = 2^k$ в любой точке $x$ можно найти за $O \left(\log_2 n\right)$ арифметических операций.

Решение задачи

Пусть $s_j = 1 + x + \ldots + x^j = \sum\limits_{i=0}^j x^i$, так что $f_n (x) = s_n$.

Тогда при $j \geqslant 1$ $s_j = s_{j-1} + x^j$, причём сама степень тоже рекуррентна: $x^j = x \cdot x^{j-1}$. Введём $p_j = x^j$ (с $p_0 = 1$). Подставляя $x^j = x p_{j-1}$, получаем систему

$$\begin{equation*} \begin{cases} s_j = s_{j-1} + x p_{j-1} \\ p_j = x p_{j-1} \end{cases} \end{equation*} \ \text{.}$$

Соберём пару в столбец $z_j = \begin{bmatrix} s_j \\ p_j \end{bmatrix}$ и введём матрицу $M = \begin{bmatrix} 1 & x \\ 0 & x \end{bmatrix}$.

Тогда $z_j = M z_{j-1} = \begin{bmatrix} 1 & x \\ 0 & x \end{bmatrix} \begin{bmatrix} s_{j-1} \\ p_{j-1} \end{bmatrix} = \begin{bmatrix} s_{j-1} + x p_{j-1} \\ x p_{j-1} \end{bmatrix}$.

Начальный столбец известен: $z_0 = \begin{bmatrix} s_o \\ p_0 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$ (ведь $s_0 = 1$, $p_0 = x^0 = 1$).

Получим по индукции равенство $z_n = M^n z_0$. База ($n = 0$) : $M^0 z_0 = z_0$ – тождество. Шаг (применяем ассоциативность умножения матриц): $z_{n+1} = Mz_n = M \left(M^n z_0\right) = M^{n+1} z_0$. Итак, $z_n = M^n z_0$, и $f_n (x) = s_n$ – верхняя компонента столбца $M^n z_0 = M^n \begin{bmatrix} 1 \\ 1 \end{bmatrix}$.

При $n = 2^k$ вычисляем $M^2, M^4, \ldots, M^{2^k} = M^n$ последовательными возведениями в квадрат $M^{2^{i+1}} = \left(M^{2^i}\right)^2$ – это $k$ умножений матриц $2 \times 2$, после чего берём $M^n z_0$.

Одно умножение матриц $2 \times 2$ – это $8$ умножений и $4$ сложения чисел, всего $12$ арифметических операций. Заключительное умножение матрицы $2 \times 2$ на столбец $M^n z_0$ – $4$ умножения и $2$ сложения, всего $6$ операций. Значит, всего

$$\underbrace{k}_\text{возведений в квадрат} \cdot \underbrace{12}_{8 + 4} + \underbrace{6}_{M^n z_0} = 12k + 6$$

операций. Это линейно по $k$, то есть $O(k)$, а $n = 2^k$ означает $k = \log_2 n$, поэтому $12k + 6 = O(k) = O(\log_2 n)$. $\square$

Замечание. Оценка $12k + 6$ – это оценка «в лоб». Можно заметить, что все степени матрицы $M = \begin{bmatrix} 1 & x \\ 0 & x \end{bmatrix}$ имеют вид $M^{2^i} = \begin{bmatrix} 1 & \ast \\ 0 & x^{2^i} \end{bmatrix}$. При возведении такой матрицы в квадрат $\begin{bmatrix} 1 & c \\ 0 & d \end{bmatrix}^2 = \begin{bmatrix} 1 & c \left(1 + d\right) \\ 0 & d^2 \end{bmatrix}$ нижний левый элемент заведомо $0$, верхний левый – $1$, и работы всего на $2$ умножения ($d^2$ и $c \cdot \left(1 + d\right)$) и $1$ сложение ($1 + d$), то есть $3$ операции вместо $12$. С учётом одного заключительного сложения ($s_n = 1 + c$, где $c$ – правый верхний элемент $M^n$) всего выходит $3k + 1$ операций. Тем не менее, на порядок $O(\log_2 n)$ это не влияет.