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

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

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

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

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

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

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

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

Частное и остатокПравить

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

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

(1)

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

$T(x)\left(Q_1(x)-<!--\; -\; -->Q_2(x)\right)=R_1(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)$$Q_{1}(x)=Q_{2}(x)$ , что также влечёт $R_1(x)=R_2(x)$$R_{1}(x)=R_{2}(x)$ , либо степень $R_1(x)-<!--\; -\; -->R_2(x)$$R_{1}(x)-R_{2}(x)$  не меньше степени $T(x)$$T(x)$ , что невозможно по определению $R(x)$$R(x)$ .

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

Данную задачу можно переписать в матричном виде, если считать, что даны $s_0,s_1,\dots <!--\; \dots \; -->,s_m$$s_{0},s_{1},\dots ,s_{m}$  и $t_0,t_1,\dots <!--\; \dots \; -->,t_n$$t_{0},t_{1},\dots ,t_{n}$ , а посчитать нужно $q_0,q_1,\dots <!--\; \dots \; -->,q_{m-<!--\; -\; -->n}$$q_{0},q_{1},\dots ,q_{m-n}$  и $r_0,r_1,\dots <!--\; \dots \; -->,r_{n-<!--\; -\; -->1}$$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)$$R(x)=S(x)-T(x)Q(x)$ , для решения задачи достаточно найти $q_{m-<!--\; -\; -->n},\dots <!--\; \dots \; -->,q_0$$q_{m-n},\dots ,q_{0}$  по первым $m-<!--\; -\; -->n+1$$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)$$T(x)$  и нулей, а решение системы эквивалентно нахождению обратной к ней.

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

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

$S^R(x)\equiv <!--\; \equiv \; -->T^R(x)Q^R(x)(\mathrm{mod}{x}^k),$$S^{R}(x)\equiv T^{R}(x)Q^{R}(x){\pmod {x^{k}}},$ 

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

$R(x)=p_0+p_{1}x+\cdots <!--\; \cdots \; -->+p_{k-<!--\; -\; -->1}{x}^{k-<!--\; -\; -->1}.$$R(x)=p_{0}+p_{1}x+\dots +p_{k-1}x^{k-1}.$ 

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

$V^R(x)\equiv <!--\; \equiv \; -->T^R(x{)}^{-<!--\; -\; -->1}(\mathrm{mod}{x}^k).$$V^{R}(x)\equiv T^{R}(x)^{-1}{\pmod {x^{k}}}.$

(4)

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

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

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

Система (3) эквивалентна уравнению $S^R(x)\equiv <!--\; \equiv \; -->T^R(x)Q^R(x)(\mathrm{mod}{x}^k)$$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 <!--\; \equiv \; -->Q^R(x)(\mathrm{mod}{x}^k)$$V^{R}(x)S^{R}(x)\equiv Q^{R}(x){\pmod {x^{k}}}$ , что в случае (4) эквивалентно системе (3).■

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

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

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

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

(5)

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

Методы решенияПравить

Деление столбикомПравить

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

$S(x)=T(x)(q_{m-<!--\; -\; -->n}{x}^{m-<!--\; -\; -->n}+Q^{\prime }(x))+R(x).$$S(x)=T(x)(q_{m-n}x^{m-n}+Q'(x))+R(x).$ 

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

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

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

ПримерПравить

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

${\begin{array}{rr}-{\begin{array}{llll}x^{3}&-12x^{2}&{\color {white}+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},$${\frac {x^{3}-12x^{2}-42}{x-3}}=x^{2}-9x-27-{\frac {123}{x-3}},$ 

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

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

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

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

$V_{k+1}=V_k-<!--\; -\; -->\frac{f(V_k)}{f^{\prime }(V_k)}=2V_k-<!--\; -\; -->A{V}_k^2,$${\textstyle V_{k+1}=V_{k}-{\frac {f(V_{k})}{f'(V_{k})}}=2V_{k}-AV_{k}^{2},}$ 

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

$V_{k+1}-<!--\; -\; -->B=A(2V_k{A}^{-<!--\; -\; -->1}-<!--\; -\; -->V_k^2-<!--\; -\; -->A^{-<!--\; -\; -->2})=-<!--\; -\; -->A(V_k-<!--\; -\; -->B{)}^2,$${\textstyle V_{k+1}-B=A(2V_{k}A^{-1}-V_{k}^{2}-A^{-2})=-A(V_{k}-B)^{2},}$ 

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

ПримерПравить

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

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

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

$Q^R(x)\equiv <!--\; \equiv \; -->(-<!--\; -\; -->12x+1)(9x^2+3x+1)\equiv <!--\; \equiv \; -->-<!--\; -\; -->108x^3-<!--\; -\; -->27x^2-<!--\; -\; -->9x+1\equiv <!--\; \equiv \; -->-<!--\; -\; -->27x^2-<!--\; -\; -->9x+1(\mathrm{mod}{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$$Q(x)=x^{2}-9x-27$ .

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

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

Каждая итерация алгоритма деления столбиком заключается в вычитании смещённого на некоторую величину $T(x)$$T(x)$  из $S(x)$$S(x)$ , что может быть выполнено за $O(n)$$O(n)$ . Так как степень $S(x)$$S(x)$ , изначально равная $m$$m$ , уменьшается, пока она не станет меньше $n$$n$ , общее время работы алгоритма можно оценить как $O(kn)$$O(kn)$ , где $k=m-<!--\; -\; -->n$$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 (англ.) // Numer. Math / 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.