0

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

2
  • dxdy.ru/topic72827.html Сложно что ли?
    – Ver Nick
    Commented 11 нояб. 2018 в 21:13
  • Вопрос был к людям, которые уже сталкивались с этой проблемой и подходил к её решению. Пару первых ссылок в гугле основательной информации не дали. Commented 11 нояб. 2018 в 21:26

1 ответ 1

2

Что означает алгоритм деления многочлена на многочлен ниже квадратичного порядка - на бином 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

4
  • x - a - бином. Нет. Деление полином на полином, а не деление полинома на бином. Деление полинома на бином по схеме Горнера. А требуется деление полинома на полином с частным и остатком. Commented 12 нояб. 2018 в 10:21
  • Ну так я же указал общедоступную книгу, в которой это есть. Добавил код.
    – MBo
    Commented 12 нояб. 2018 в 10:37
  • Данный алгоритм уже реализовывал. Он имеет квадратичную сложность. Интересует именно линейно-логарифмическая. За книгу спасибо, гляну. Commented 12 нояб. 2018 в 10:37
  • Тогда, видимо, через FFT нужно (через deconvolution, numpy)
    – MBo
    Commented 12 нояб. 2018 в 10:38

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.