none
Деление полиномов (многочленов) C#

    Вопрос

  • В Matlab есть замечательная функция для деления многочленов:

    DECONV (Matlab)

    Функция [q, r] = deconv(c, a) реализует деление полинома c на полином a; частное от деления возвращается в виде вектора q, остаток - в виде вектора r, так что выполняется соотношение c = conv(q, a) + r.

    Нашел сайт, где в онлайне реализовано деление полиномов:

    Деление полиномов

    Нашел пример кода за 2010 год


    Можете подсказать, есть ли в .Net функция или класс, который делает то же самое что и DECONV в Matlab (делит многочлен на многочлен и находит остаток от деления)?

    Использую C#.

    14 сентября 2012 г. 7:42

Ответы

  • Пока пил чай, написал вот такую библиотеку для деления многочлена на многочлен:

    /// <summary>
    /// Класс, для реализации метода деления многочлена на многочлен
    /// </summary>
    public static class MyMath
    {
        /// <summary>
        /// Метод деления многочлена на многочлен
        /// </summary>
        /// <param name="dividend">Коэффициенты многочлена делимого, индекс в массиве - степень элемента многочлена</param>
        /// <param name="divisor">Коэффициенты многочлена делителя, индекс в массиве - степень элемента многочлена</param>
        /// <param name="quotient">Коэффициенты многочлена частного, индекс в массиве - степень элемента многочлена</param>
        /// <param name="remainder">Коэффициенты многочлена остатка, индекс в массиве - степень элемента многочлена</param>
        public static void Deconv(double[] dividend, double[] divisor, out double[] quotient, out double[] remainder)
        {
            if (dividend.Last() == 0)
            {
                throw new ArithmeticException("Старший член многочлена делимого не может быть 0");
            }
            if (divisor.Last() == 0)
            {
                throw new ArithmeticException("Старший член многочлена делителя не может быть 0");
            }
            remainder = (double[])dividend.Clone();
            quotient = new double[remainder.Length - divisor.Length + 1];
            for (int i = 0; i < quotient.Length; i++)
            {
                double coeff = remainder[remainder.Length - i - 1] / divisor.Last();
                quotient[quotient.Length - i - 1] = coeff;
                for (int j = 0; j < divisor.Length; j++)
                {
                    remainder[remainder.Length - i - j - 1] -= coeff * divisor[divisor.Length - j - 1];
                }
            }
        }
    }

    Пример использования, можете посмотреть у меня в блоге.

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

    • Помечено в качестве ответа sg6336 14 сентября 2012 г. 13:53
    14 сентября 2012 г. 13:11
    Отвечающий

Все ответы

  • Скорее всего нет встроенных подобных возможностей, так как тема данная спецефическая и уже выходит за пределы общих возможностей. А пример который Вы привели вполне себе рабочий, можно его доделать. Может в сети есть библиотеки с подобной реализацией и более большими возможностями например посмотрите сюда.
    14 сентября 2012 г. 8:46
    Модератор
  • Спасибо, за ссылку. Буду думать. Данная задача существует уже очень давно. Может кто-то знает библиотеку с реализацией?

    14 сентября 2012 г. 9:43
  • На сколько я помню математику, там алгоритм достаточно тривиален. Не быстрее будет его написать?
    14 сентября 2012 г. 9:53
    Отвечающий
  • Понимаете, мне нужно написать программу, которая находит порядки образующих элементов неприводимых многочленов над GF(n). Где n = 2,3,5,7. Причем для степеней от 2 до 27. Любой «тормоз» в реализации выльется в дополнительные минуты или часы расчетов.

    Видно, что для полинома 8-й степени программа проводит вычисления за 4 секунды, а для полинома 16-й степени считает больше часа. Можете себе представить затраты времени для расчетов полиномов в 27-й степени.

    Сейчас написал для GF(2) рабочую программу. Т.к. это двоичная система и есть более быстрые алгоритмы для нее. А вот в троичной системе возникли сложности.

    Т.е. пишу программу с использованием таких операций, как «сложение по модулю 3». Но, традиционное решение через деление многочленов.

    Подытожу:  Вы правы, алгоритм тривиальный (когда на бумаге). А мне нужна быстрая реализация этого алгоритма.


    • Изменено sg6336 14 сентября 2012 г. 12:12
    14 сентября 2012 г. 10:27
  • Пока пил чай, написал вот такую библиотеку для деления многочлена на многочлен:

    /// <summary>
    /// Класс, для реализации метода деления многочлена на многочлен
    /// </summary>
    public static class MyMath
    {
        /// <summary>
        /// Метод деления многочлена на многочлен
        /// </summary>
        /// <param name="dividend">Коэффициенты многочлена делимого, индекс в массиве - степень элемента многочлена</param>
        /// <param name="divisor">Коэффициенты многочлена делителя, индекс в массиве - степень элемента многочлена</param>
        /// <param name="quotient">Коэффициенты многочлена частного, индекс в массиве - степень элемента многочлена</param>
        /// <param name="remainder">Коэффициенты многочлена остатка, индекс в массиве - степень элемента многочлена</param>
        public static void Deconv(double[] dividend, double[] divisor, out double[] quotient, out double[] remainder)
        {
            if (dividend.Last() == 0)
            {
                throw new ArithmeticException("Старший член многочлена делимого не может быть 0");
            }
            if (divisor.Last() == 0)
            {
                throw new ArithmeticException("Старший член многочлена делителя не может быть 0");
            }
            remainder = (double[])dividend.Clone();
            quotient = new double[remainder.Length - divisor.Length + 1];
            for (int i = 0; i < quotient.Length; i++)
            {
                double coeff = remainder[remainder.Length - i - 1] / divisor.Last();
                quotient[quotient.Length - i - 1] = coeff;
                for (int j = 0; j < divisor.Length; j++)
                {
                    remainder[remainder.Length - i - j - 1] -= coeff * divisor[divisor.Length - j - 1];
                }
            }
        }
    }

    Пример использования, можете посмотреть у меня в блоге.

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

    • Помечено в качестве ответа sg6336 14 сентября 2012 г. 13:53
    14 сентября 2012 г. 13:11
    Отвечающий