Деление многочленов

Деление многочленов — операция деления с остатком в евклидовом кольце многочленов от одной переменной над некоторым полем. Наивный алгоритм, реализующий эту операцию, представляет собой обобщенную форму деления чисел столбиком, легко реализуемую вручную.

Для любых многочленов $f(x)$ и $g(x)$, $g(x)\neq 0$, существуют единственные многочлены $q(x)$ и $r(x)$, такие что

${\frac {f(x)}{g(x)}}=q(x)+{\frac {r(x)}{g(x)}}$,

причем $r(x)$ имеет более низкую степень, чем $g(x)$.

Целью алгоритмов деления многочленов является нахождение частного $q(x)$ и остатка $r(x)$ для заданных делимого $f(x)$ и ненулевого делителя $g(x)$.

Постановка задачи

Задача о делении многочленов с остатком может быть сформулирована в следующих эквивалентных постановках.

Частное и остаток

Многочлены $S(x)=s_{0}+s_{1}x+\dots +s_{m}x^{m}$ степени $m$ и $T(x)=t_{0}+t_{1}x+\dots +t_{n}x^{n}$ степени $n$, заданы своими коэффициентами. Необходимо найти частное $Q(x)=q_{0}+q_{1}x+\dots +q_{m-n}x^{m-n}$ и остаток $R(x)=r_{0}+r_{1}x+\dots +r_{n-1}x^{n-1}$, такие что

$S(x)=T(x)Q(x)+R(x).$ (1)

Определённые таким образом многочлены $Q(x)$ и $R(x)$ единственны — если допустить, что у уравнения (1) существует два решения $Q_{1}(x),R_{1}(x)$ и $Q_{2}(x),R_{2}(x)$, то

$T(x)\left(Q_{1}(x)-Q_{2}(x)\right)=R_{1}(x)-R_{2}(x),$

из чего следует, что либо $Q_{1}(x)=Q_{2}(x)$, что также влечёт $R_{1}(x)=R_{2}(x)$, либо степень $R_{1}(x)-R_{2}(x)$ не меньше степени $T(x)$, что невозможно по определению $R(x)$.

Матричная постановка

Данную задачу можно переписать в матричном виде, если считать, что даны $s_{0},s_{1},\dots ,s_{m}$ и $t_{0},t_{1},\dots ,t_{n}$, а посчитать нужно $q_{0},q_{1},\dots ,q_{m-n}$ и $r_{0},r_{1},\dots ,r_{n-1}$ такие что

${\begin{bmatrix}s_{m}\\\vdots \\s_{n+1}\\s_{n}\\s_{n-1}\\\vdots \\s_{0}\end{bmatrix}}={\begin{bmatrix}t_{n}&\dots &0&0\\\vdots &\ddots &\vdots &\vdots \\\dots &\dots &t_{n}&0\\\dots &\dots &t_{n-1}&t_{n}\\\dots &\dots &t_{n-2}&t_{n-1}\\\vdots &\ddots &\vdots &\vdots \\0&\dots &0&t_{0}\end{bmatrix}}{\begin{bmatrix}q_{m-n}\\\vdots \\q_{1}\\q_{0}\end{bmatrix}}+{\begin{bmatrix}0\\\vdots \\0\\0\\r_{n-1}\\\vdots \\r_{0}\end{bmatrix}}_{\textstyle .}$ (2)

Обратная тёплицева матрица

В силу того, что $R(x)=S(x)-T(x)Q(x)$, для решения задачи достаточно найти $q_{m-n},\dots ,q_{0}$ по первым $m-n+1$ уравнениям системы. Если рассматривать только эти уравнения, задача принимает вид

${\begin{bmatrix}s_{m}\\\vdots \\s_{n+1}\\s_{n}\end{bmatrix}}={\begin{bmatrix}t_{n}&\dots &0&0\\\vdots &\ddots &\vdots &\vdots \\\dots &\dots &t_{n}&0\\\dots &\dots &t_{n-1}&t_{n}\end{bmatrix}}{\begin{bmatrix}q_{m-n}\\\vdots \\q_{1}\\q_{0}\end{bmatrix}}_{\textstyle .}$ (3)

Матрица данной системы уравнений является нижнетреугольной и тёплицевой, составленной из старших коэффициентов $T(x)$ и нулей, а решение системы эквивалентно нахождению обратной к ней.

Обратный многочлен по модулю

Пусть $S^{R}(x)=x^{m}S(x^{-1})=s_{m}+s_{m-1}x+\dots +s_{0}x^{m}$ и $T^{R}(x)=x^{n}T(x^{-1})=t_{n}+t_{n-1}x+\dots +t_{0}x^{n}$ — многочлены, полученные из $S(x)$ и $T(x)$ разворотом последовательности коэффициентов. Систему уравнений (3) можно сформулировать как

$S^{R}(x)\equiv T^{R}(x)Q^{R}(x){\pmod {x^{k}}},$

где $k=m-n+1$, а ${\bmod {x}}^{m-n}$ означает, что остатки от деления многочленов $S^{R}(x)$ и $T^{R}(x)Q^{R}(x)$ на $x^{k}$ равны. Деление многочлена $P(x)$ на $x^{k}$ может быть представлено как $P(x)=x^{k}Q(x)+R(x)$, поэтому остаток $R(x)$ равен многочлену, полученному из первых $k$ коэффициентов $P(x)$, то есть,

$R(x)=p_{0}+p_{1}x+\dots +p_{k-1}x^{k-1}.$

Если многочлены $S^{R}(x)$ и $T^{R}(x)$ известны, то $Q^{R}(x)\equiv S^{R}(x)T^{R}(x)^{-1}{\pmod {x^{k}}}$, где $T^{R}(x)^{-1}$ — обратный к $T^{R}(x)$ многочлен в кольце остатков по модулю $x^{k}$. Таким образом, поиск $Q(x)$ может быть сведён к нахождению $V(x)=v_{0}+v_{1}x+\dots +v_{k}x^{k}$, такого что

$V^{R}(x)\equiv T^{R}(x)^{-1}{\pmod {x^{k}}}.$ (4)

Данная постановка позволяет также находить обратную матрицу в системе (3):

Пусть $T$ — матрица размера $k$ из (3). Тогда $T^{-1}$ — нижнетреугольная тёплицева матрица, первый столбец которой равен ${\begin{bmatrix}v_{k-1}&v_{k-2}&\dots &v_{0}\end{bmatrix}}^{T}$, где $v_{0},\dots ,v_{k-1}$ — коэффициенты $V(x)$ из (4).

Доказательство

Система (3) эквивалентна уравнению $S^{R}(x)\equiv T^{R}(x)Q^{R}(x){\pmod {x^{k}}}$. Соответственно, система

${\begin{bmatrix}v_{m-n}&\dots &0&0\\\vdots &\ddots &\vdots &\vdots \\v_{1}&\dots &v_{m-n}&0\\v_{0}&\dots &v_{m-n-1}&v_{m-n}\end{bmatrix}}{\begin{bmatrix}s_{m}\\\vdots \\s_{n+1}\\s_{n}\end{bmatrix}}={\begin{bmatrix}q_{m-n}\\\vdots \\q_{1}\\q_{0}\end{bmatrix}}$

может быть представлена в виде $V^{R}(x)S^{R}(x)\equiv Q^{R}(x){\pmod {x^{k}}}$, что в случае (4) эквивалентно системе (3).■

В силу произвольности многочлена $T(x)$, определяющего элементы $T$, данный факт позволяет находить обратную к произвольной тёплицевой нижнетреугольной матрице.

Формальные степенные ряды

Уравнение $S^{R}(x)=T^{R}(x)Q^{R}(x)$ можно рассматривать не только по модулю $x^{m-n}$, но и как равенство в кольце формальных степенных рядов. Пусть $s(x)$ и $t(x)$ — формальные степенные ряды, совпадающие с многочленами $S^{R}(x)$ и $T^{R}(x)$. Если в таких терминах найти формальный ряд

$q(x)={\frac {s(x)}{t(x)}},$ (5)

то его коэффициенты при младших $m-n+1$ степенях будут соответствовать искомому многочлену $Q^{R}(x)$. Такой подход также позволяет рассмотреть задачу (2) как систему с бесконечно продлённой тёплицевой матрицей и бесконечно продлённым столбцом $q$, в которой исключён столбец остатков $r$. Решение первых $h$ строк такой системы даст первые $h$ коэффициентов ряда $q(x)$, а именно $q_{m-n},q_{m-n-1},\dots ,q_{m-n-h+1}$. В то же время, работа со степенными рядами в целом, при которой интерес представляют только первые $h$ коэффициентов ряда (например, из-за ограниченности доступной памяти), эквивалентна работе с многочленами, операции над которыми производятся в кольце остатков по модулю $x^{h}$. В частности, поиск первых $h$ коэффициентов $q(x)$ эквивалентен решению уравнения $s(x)\equiv t(x)q(x){\pmod {x^{h}}}$.

Методы решения

Деление столбиком

В ходе алгоритма, коэффициенты при старших степенях $S(x)$ последовательно зануляются за счёт вычитания из него $T(x)$, умноженного на некоторую степень $x$ с коэффициентами, которые затем образуют частное $Q(x)$. Изначально, коэффициент $q_{m-n}$ определяется равным ${\textstyle {\frac {s_{m}}{t_{n}}}}$. Если разложить $Q(x)=q_{m-n}x^{m-n}+Q'(x)$, то

$S(x)=T(x)(q_{m-n}x^{m-n}+Q'(x))+R(x).$

С помощью замены $S'(x)=S(x)-q_{m-n}x^{m-n}T(x)$, данное уравнение приобретает вид

$S'(x)=T(x)Q'(x)+R(x),$

аналогичный уравнению (1). При этом $m$-й коэффициент $S'(x)$, по определению $q_{m-n}$, равен $0$, поэтому степень $S'(x)$ будет меньше, чем степень $S(x)$. Процедура повторяется, пока степень $S'(x)$ не станет меньше степени $T(x)$, что будет означать, что очередной $S'(x)$ равен $R(x)$ и для него $Q'(x)=0$.

Пример

Пусть $S(x)=x^{3}-12x^{2}-42$ и $T(x)=x-3$. Для данных многочленов, деление столбиком $S(x)$ на $T(x)$ может быть записано как

${\begin{array}{rr}-{\begin{array}{llll}x^{3}&-12x^{2}&{\color {gray}+0x}&-42\\x^{3}&-3x^{2}&&\\\hline \end{array}}&{\begin{array}{|l}x-3\\\hline x^{2}-9x-27\end{array}}\\-{\begin{array}{lll}-9x^{2}&&-42\\-9x^{2}&+27x&\\\hline \end{array}}&\\-{\begin{array}{ll}-27x&-42\\-27x&+81\\\hline \end{array}}&\\-123\end{array}}$

Таким образом,

${\frac {x^{3}-12x^{2}-42}{x-3}}=x^{2}-9x-27-{\frac {123}{x-3}},$

то есть, многочлен $Q(x)=x^{2}-9x-27$ — частное деления, а $R(x)=-123$ — остаток.

Алгоритм Зивекинга — Кона

Основная статья: Лемма Гензеля

В 1972 году Мальте Зивекинг предложил алгоритм для поиска решения $B(x)$ уравнения $A(x)\cdot B(x)=C(x){\pmod {x^{n+1}}}$ при заданных $A(x)$ и $C(x)$. В 1974 году Кон Сянчжун показал, что при $C(x)=1$ алгоритм представляет собой итерацию метода Ньютона для $f(V)=V^{-1}-A$. При таком подходе, итерация принимает вид

${\textstyle V_{k+1}=V_{k}-{\frac {f(V_{k})}{f'(V_{k})}}=2V_{k}-AV_{k}^{2},}$

Где $f'(V_{k})=-V_{k}^{-2}$ обозначает производную функции $f(V)$ в точке $V_{k}$. Для оценки точности алгоритма, можно оценить разность

${\textstyle V_{k+1}-B=A(2V_{k}A^{-1}-V_{k}^{2}-A^{-2})=-A(V_{k}-B)^{2},}$

из чего следует, что если $V_{k}-B$ делится на $x^{t}$ (что равносильно тому, что первые $t$ коэффициентов $V_{k}$ определены корректно), то $V_{k+1}-B$ будет делиться уже на $x^{2t}$. Таким образом, при начальном условии $V_{0}=b_{0}=a_{0}^{-1}$, каждая итерация удваивает число точно определённых коэффициентов $B(x)$. Поэтому для вычисления $A(x)^{-1}{\pmod {x^{n+1}}}$ достаточно $O(\log n)$ итераций. Применение быстрого преобразования Фурье к умножению многочленов в формуле выше позволяет прийти к итоговому времени работы $O(n\log n)$, что существенно улучшает оценку для обычного длинного умножения.

Пример

Пусть $S(x)=x^{3}-12x^{2}-42$ и $T(x)=x-3$. В силу (4), необходимо найти $Q^{R}(x)=(-42x^{3}-12x+1)(-3x+1)^{-1}{\pmod {x^{3}}}$. Обратный многочлен $V(x)=(-3x+1)^{-1}{\pmod {x^{3}}}$ ищется следующим образом:

1. Начальное приближение определяется как ${\textstyle V_{0}={\frac {1}{T^{R}(0)}}=1}$;
2. Первое приближение определяется как $V_{1}=V_{0}(2-(-3x+1)V_{0})=3x+1$;
3. Второе приближение определяется как $V_{2}=(3x+1)(2-(-3x+1)(3x+1))=(3x+1)(9x^{2}+1)=27x^{3}+9x^{2}+3x+1$.

В силу свойств метода Ньютона, первые $2^{2}=4$ коэффициента $V_{2}(x)$ определены верно. Так как дальнейшие вычисления происходят по модулю $x^{3}$, коэффициенты при более высоких степенях можно отбросить. Отсюда

$Q^{R}(x)\equiv (-12x+1)(9x^{2}+3x+1)\equiv -108x^{3}-27x^{2}-9x+1\equiv -27x^{2}-9x+1{\pmod {x^{3}}},$

в силу чего $Q(x)=x^{2}-9x-27$.

Анализ алгоритмов

Для оценки эффективности различных методов используется арифметическая схемная сложность — суммарное количество операций сложения, умножения, вычитания и деления над полем комплексных чисел, которые необходимо произвести в ходе работы алгоритма. Также оценивается количество параллельных шагов, требуемых для многопроцессорной реализации алгоритма, в предположении, что каждый процессор на любом шаге может выполнять не более одной операции.

Каждая итерация алгоритма деления столбиком заключается в вычитании смещённого на некоторую величину $T(x)$ из $S(x)$, что может быть выполнено за $O(n)$. Так как степень $S(x)$, изначально равная $m$, уменьшается, пока она не станет меньше $n$, общее время работы алгоритма можно оценить как $O(kn)$, где $k=m-n$.

См. также

• Теорема Безу
• Правило Руффини
• Базис Грёбнера
• Наибольший общий делитель двух многочленов
• Синтетическое деление

Литература

• Bini D., Pan V. Polynomial division and its computational complexity (англ.) // Journal of Complexity — Elsevier BV, 1986. — Vol. 2, Iss. 3. — P. 179—203. — ISSN 0885-064X; 1090-2708 — doi:10.1016/0885-064X(86)90001-4
• Knuth D. The Art of Computer Programming (англ.): Seminumerical Algorithms — 3 — Addison-Wesley, 1997. — Vol. 2. — 784 p. — ISBN 978-0-201-89684-8
• Kung H. T. On computing reciprocals of power series (англ.) // Numerische Mathematik / F. Brezzi — Springer Science+Business Media, 1974. — Vol. 22, Iss. 5. — P. 341—348. — ISSN 0029-599X; 0945-3245 — doi:10.1007/BF01436917
• Sieveking M. An algorithm for division of powerseries (англ.) // Computing — Springer Science+Business Media, 1972. — Vol. 10, Iss. 1-2. — P. 153—156. — ISSN 0010-485X; 1436-5057 — doi:10.1007/BF02242389
• Schönhage A. Variations on Computing Reciprocals of Power Series (англ.) // Algorithms Seminar, 2000-2001 / F. Chyzak — Institut National de Recherche en Informatique et en Automatique, 2001. — P. 81—84. — 197 p.