Требуется литература или любая другая информация в данном вопросе. В частности, алгоритм деления многочлена на многочлен ниже квадратичного порядка (обычный уголок не подходит). Деление многочлена на многочлен должно просчитывать частное и остаток от деления.
-
dxdy.ru/topic72827.html Сложно что ли?– Ver NickCommented 11 нояб. 2018 в 21:13
-
Вопрос был к людям, которые уже сталкивались с этой проблемой и подходил к её решению. Пару первых ссылок в гугле основательной информации не дали.– Khetag AbramovCommented 11 нояб. 2018 в 21:26
Добавить комментарий
|
1 ответ
Что означает алгоритм деления многочлена на многочлен ниже квадратичного порядка
- на бином x-a
? Для этого есть процедура "synthetic division"
//деление полинома, коэффициенты которого хранятся в массиве CC[]
//на (x - tx)
//источник - Numerical Recipes in C, chapter 5
var
CC: array of Double;
rem, temp, tx: double;
n, i: integer;
begin
CC := [5, 3, 2]; //2x^2+3x+5
n := Length(CC) - 1;
tx := 1; //x-1
rem := CC[n];
CC[n] := 0;
for i := n - 1 downto 0 do
begin
temp := CC[i];
CC[i] := rem;
rem := temp + rem * tx;
end;
Memo1.Lines.Add(Format('[%2.0f, %2.0f, %2.0f], rem = %2.0f',[CC[0], CC[1], CC[2], rem]));
//теперь степень полинома понижена на единицу
//коэффициенты в том же CC[], числовой остаток в rem
>> [ 5, 2, 0], rem = 10
2x^2+3x+5 = (2x+5)*(x-1) + 10
В указанной книге есть и деление на полином произвольной степени poldiv
с получением также коэффициентов полинома-остатка. С++ вариант (u / v
, так что u = v * q + r
)
void NR::poldiv(Vec_I_DP &u, Vec_I_DP &v, Vec_O_DP &q, Vec_O_DP &r)
{
int k,j;
int n=u.size()-1;
int nv=v.size()-1;
for (j=0;j<=n;j++) {
r[j]=u[j];
q[j]=0.0;
}
for (k=n-nv;k>=0;k--) {
q[k]=r[nv+k]/v[nv];
for (j=nv+k-1;j>=k;j--) r[j] -= q[k]*v[j-k];
}
for (j=nv;j<=n;j++) r[j]=0.0;
}
Для реализации более быстрого алгоритма потребуется использование FFT (быстрое преобразование Фурье). Умножение полиномов (это достаточно популярный алгоритм) с его применением делается через свертку (convolution), а деление - через деконволюцию (deconvolution).
Matlab
Scipy
-
x - a - бином. Нет. Деление полином на полином, а не деление полинома на бином. Деление полинома на бином по схеме Горнера. А требуется деление полинома на полином с частным и остатком. Commented 12 нояб. 2018 в 10:21
-
Ну так я же указал общедоступную книгу, в которой это есть. Добавил код.– MBoCommented 12 нояб. 2018 в 10:37
-
Данный алгоритм уже реализовывал. Он имеет квадратичную сложность. Интересует именно линейно-логарифмическая. За книгу спасибо, гляну. Commented 12 нояб. 2018 в 10:37
-