Задача 6

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

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

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

Рассмотрим последовательность $g_k \left(x\right) = 1 + x + \ldots + x^{2^k - 1}$. Докажем рекуррентное соотношение $g_{k+1} \left(x\right) = \left(1 + x^{2^k}\right) g_k \left(x\right)$.

Действительно, $g_{k+1} \left(x\right) = 1 + x + \ldots + x^{2^{k+1} - 1} = \left(1 + x + \ldots + x^{2^k - 1}\right) + x^{2^k} \left(1 + x + \ldots + x^{2^k - 1}\right) = \left(1 + x^{2^k}\right) g_k \left(x\right)$. Кроме того, $g_0 \left(x\right) = 1$.

Теперь пусть $n = 2^k$. Тогда $f_n \left(x\right) = 1 + x + \ldots + x^{2^k} = g_k \left(x\right) + x^{2^k}$.

Покажем, что $g_k \left(x\right)$ можно вычислить за $O\left(k\right)$ арифметических операций.

Сначала последовательно вычисляем степени $x^2, \, x^4, \, x^8, \, \ldots, \, x^{2^k}$ последовательным возведением в квадрат: $x^{2^{i+1}} = \left(x^{2^i}\right)^2$. Для этого требуется $k$ умножений.

После этого последовательно вычисляем значения $g_0 \left(x\right), \, g_1 \left(x\right), \, \ldots, \, g_k \left(x\right)$ по рекуррентной формуле $g_{i+1} \left(x\right) = \left(1 + x^{2^i}\right) g_i \left(x\right), \; i = 0, \, 1, \, \ldots, \, k - 1$. На каждом шаге требуется константное число арифметических операций: одно сложение и одно умножение. Следовательно, для вычисления всех $g_i \left(x\right)$ требуется $O\left(k\right)$ арифметических операций.

Таким образом, общее число операций имеет порядок $O\left(k\right) = O\left(\log_2 n\right)$.

Наконец, $f_n \left(x\right) = g_k \left(x\right) + x^{2^k}$, поэтому значение $f_n \left(x\right)$ также вычисляется за $O\left(\log_2 n\right)$ арифметических операций. $\square$