Вычисление многочлена (ч2)

retweet
28.10.2011 12:00


Это вторая часть рассказа о вычислении многочлена в точке. Первую часть можно найти тут.

Здесь мы рассмотрим алгоритм Патерсона и Стокмеера, который делает наименьшее (из известных мне) количество умножений, при условии, что при запросах к вычислению значения можно использовать только арифметические операции (*, +, -). На стадии предподсчета понадобится еще и деление. Можно ли сделать это быстрее при таких ограничениях - пока открытый вопрос [1].

К сожалению, еще одним необходимимым фактором является то, что поле над которым рассматриваются многочлены должно быть нулевой характеристики. Грубо говоря, это означает, что все элементы вида (1 + 1 + ... + 1) различны. Хорошей новостью является, что подойдут как вещетвенные, так и комплексные и рациональные числа. Из часто встречаемых на практике отпадает только модулярная арифметика.

Заявленное количество умножений n/2 + 2log(n), сложений 3n/2 - 1, на один запрос вычисления многочлена. (здесь и далее все логарифмы по двоичному основанию).

Для начала предположим, что в данном нам многочлене ровно n = 2^k слагаемых и коэффициент при старшей степени равен единице. Т.е. многочлен приведенный степени n - 1.

Тогда его можно удобно поделить на две половины, тоже длиной степени двойки и воспользоваться известным принципом "разделяй и властвуй":

\renewcommand \ntwo{\frac{n}{2}} f(x) = a_0 + a_1x + \dots + a_{\ntwo-1}x^{\ntwo-1} + x^{\ntwo}\left(a_{\ntwo} + \dots + a_{n-2}x^{\ntwo-2} + x^{\ntwo-1}\right)
к правой части никаких замечаний нет, но у левой старший коэффициент не равен единице. Но это легко исправить, заметив, что в скобках "почти такой же" многочлен:
\renewcommand \ntwo{\frac{n}{2}} f(x) = b_0 + \dots + b_{\ntwo-2}x^{\ntwo-2} + x^{\ntwo-1} + (x^{\ntwo} + \delta) \left(a_{\ntwo} + \dots + a_{n-2}x^{\ntwo-2} + x^{\ntwo-1}\right) \\ = \left(b_0 + \delta a_{\ntwo}\right) + \dots + \left(b_{\ntwo-2} + \delta a_{n-2}\right) x^{\ntwo-2} + \left(1 + \delta\right)x^{\ntwo-1} + \\ x^{\ntwo} \left(a_{\ntwo} + \dots + a_{n-2}x^{\ntwo-2} + x^{\ntwo-1}\right)
Если сравнить это с предыдущим выражением, понятно, что неизвестные выражаются по следующим формулам:
\renewcommand \ntwo{\frac{n}{2}} \delta = a_{\ntwo - 1} - 1 \\ b_i = a_i - \delta a_{i + \ntwo},\quad 0 \le i < \ntwo - 1
Эти коэффициенты и находятся на стадии предподсчета. А при вычислении многочлена в точке мы просто счтаем его на левой половине, на првой и складываем (все иксы в степени 2^i подсчитаем, всего за log(n) умножений, и они нам еще потом понадобятся!).

Количество умножений выражается реккурентной формулой M(k) = 2 * M(k - 1) + 1, где M(k) - количество умножений на многочлене длины 2^k. Приведенный многочлен степени один (т.е. длины 2 = 2^1) высчитывается без умножений, т.е. M(1) = 0.
Решая реккурентное соотношение, получаем: M(k) = 2^{k-1} - 1 = n / 2 - 1.
Если мы хотим, чтобы начальный многочлен был общего вида, а не приведенный, то понадобится еще одно умножение (а на стадии предподсчета нормировка, т.е. деление всех коэф. на старший). Итого на вычисление многочлена длины n = 2^k требуется n / 2 умножений.

Аналогично для сложения: A(k) = 2 * A(k - 1) + 2, A(1) = 1. Т.о. A(k) = 3*2^{k-1} - 2 = 3n/2 - 2.

Формулы для реккурентных соотношений легко доказываются по индукции, если знать ответ, или же можно использовать производящие ряды и явно получить их =)

Теперь у нас многочлен общего вида, и в нем ровно n слагаемых. Допустим в битовой записи числа n ровно k единичек (k ~ log(n)). Тогда можно представить число n в виде суммы соответствующих степеней двоек, а сам многочлен разложить в виде:

n = 2^{i_1} + 2^{i_2} + \dots + 2^{i_k} = p_1 + \dots + p_k, \quad \underbrace{x^2, x^4, \dots, x^{2^{i_k}}}_{\log_2n} \\ \underbrace{a_0 + a_1x + \dots + a_{p_1-1}x^{p_1-1}}_{p_1} + x^{p_1}\underbrace{\left(a_{p_1} + a_{p_1 + 1}x + \dots + a_{p_1+p_2-1}x^{p_2-1}\right)}_{p_2} + \\ \dots \\ + x^{p_1+\dots+p_{k-1}}\underbrace{\left(a_{p_1+\dots+p_{k-1}} + \dots + a_{p_1+\dots+p_{k}-1}x^{p_k-1}\right)}_{p_k}= \\ \sum\limits_{i=0}^{p_1-1}a_ix^i + x^{p_1}\left(\sum\limits_{i=0}^{p_2-1}a_{i+p_1}x^i + \dots + x^{p_k}\left(\sum\limits_{i=0}^{p_k-1}a_{i+p_1+\dots+p_{k-1}}x^i\right) \dots \right)

Каждый "маленький многочлен" длиной pj мы вычисляем за pj / 2 умножений.
Стало быть, всего (p1 + ... + pk) / 2 = n / 2 умножений.
Еще один log(n) - вычисление степеней x, второй - умножение на них, соответствующих частей выражения.
Итого n/2 + 2log(n).
Аналогично со сложениями 3n/2 - log(n).

Ни один "из маленьких" многочленов не должен иметь нулевой старший коэффициент, а то его длина будет меньше степени двойки, предыдущая часть не сможет его нормировать и сломается. Но если какой-то коэффициент многочлена нулевой, на стадии предподсчета легко сдвинуть x' = x + c, и пересчитать коэффициенты многочлена. Это добавит нам еще одно сложение в копилку при вычислении запроса (сдвиг исходного x).

Ну вот и все, спасибо за внимание, тем дочитал аж до сюда! Я могу вам предложить интереснейшую литературу по этому и другим вопросам алгебраической сложности:
[1] P. Burgisser, M. Clausen, M. Amin Shokrouahi, Agebraic Complexity Theory.