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

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

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

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

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

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

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

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

${\displaystyle S(x)=T(x)Q(x)+R(x).}$

(1)

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

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

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

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

${\displaystyle {\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)

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

${\displaystyle {\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)

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

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

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

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

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

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

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

(4)

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

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

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

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

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

(5)

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

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

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

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

${\displaystyle S'(x)=T(x)Q'(x)+R(x),}$

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}},}$

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

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

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

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

• 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.