Griboks
@Griboks

Перемножение полиномов?

Необходимо на C# перемножить два полинома вида a0*b^0+a1*b^1+... Могут быть произвольной длины. Хранятся как массив коэффициентов. Сами коэффициенты могут быть от 1 до ulong.MaxValue (больше шарп не позволяет) - целые числа. Так же можно использовать только system и коллекции.
Проблема в том, что если тупо перемножать, возможно переполнение памяти.
Как перемножить полиномы без ошибки памяти и какой алгоритм самый быстрый?

P.s.
Это не домашнее задание или курсовая работа!
  • Вопрос задан
  • 785 просмотров
Пригласить эксперта
Ответы на вопрос 3
Punk_Joker
@Punk_Joker
Software Engineer в ВО Овен
x67
@x67
(a1+a2+...+an)*(b1+b2+...+bm)=b1*(a1+...+an)+b2*(a1+...+an)+...+bm*(a1+...+an)

в полиноме an=kn*x^n, к примеру, тогда:
bm*an=kbm*kan*x^(n+m) - это простейшая ячейка операции, так сказать. bm*(a1+...+an) состоит из n таких ячеек, а их сумма будет ячейкой второго уровня. Ячеек второго уровня будет m штук, а их сумма - ваш результат, назовем его ячейкой третьего уровня. Собственно вам надо инкрементально считать ячейку второго уровня, после чего инкрементально же ее прибавлять к ячейке третьего уровня. Тогда предел необходимой памяти будет стремиться не к m*n+с, а к с, где с - константа
Ответ написан
sgjurano
@sgjurano
Разработчик
Быстрое преобразование Фурье позволит сделать это за О(nlogn).
https://m.habrahabr.ru/post/113642/
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы