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

Question

[Griboks]

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

P.s.
Это не домашнее задание или курсовая работа!

Answer 1

[Сергей Сахно]

Может поможет
https://habrahabr.ru/post/207754/

Comments

[Griboks]

Увы, но уже читал, и не помогло(

Answer 2

[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+с, а к с, где с - константа

Comments

[Griboks]

Неплохая идея, хоть это и есть элементарная формула умножения £i=1:n(£k=1:m(ai*bi*x^(i+k))). Вопрос в другом: произведение ai*bi должно укладываться в память переменной. Например, если переменная состоит из 2 бит, то 2*3 вызовет исключение, хотя по отдельности они умещаются в 2бита.

[x67]

Griboks: ответ очевиден, результат должен записываться в переменную с удвоенным количеством бит. Если бы вы писали на ассемблере, то сами так и сделали бы. Еще как более универсальный вариант (для совсем больших чисел) - использовать символьные вычисления. Библиотеки найти не проблема, уверен в готовых решениях уже используется вся мощь возможной оптимизации этого подхода.

[Griboks]

x67: рано или поздно большие встроенные типы закончатся. Смысл в том, что бы не использовать готовые решения.

[x67]

Griboks: вы пытаетесь придумать условия, с которыми решение не справится. Это полезно, но когда у вас уже есть готовое решение. Так можно найти много факторов, почему в какой-то момент вы не сможете посчитать эти чертовы полиномы, но надо исходить из реальных требований, пусть даже помноженных на два. Для таких требований встроенных типов хватит. Если не хватит, используйте символьные вычисления (умножение в столбик и тд). Реализовать такие вычисления вы можете сами, библиотеки просто позволили бы не создавать велосипед.
П.с. Пардон, вместо символьных вычислений правильнее использовать термин "длинная арифметика"

[Griboks]

x67: ничего я не выдумываю, перечитайте шапку! Проблема в ограниченности коэффициентов как в множителях, так и в произведении.

Нельзя оптимизировать умножение, если не определена сама операция. А она не определена для чисел, произведение которых больше 2^64.

Попрошу заметить, что библиотеки тоже не на манне небесной написаны.

Велосипед изобретать умею, буду и всем советую.

[x67]

Griboks: Повторяю, задача, описанная вами, решаема. Если не придумывать новых "А если". Даже если вам не хватает 2^64, вы можете использовать длинную арифметику. При использовании библиотек все операции длинной арифметики будут определены в этих библиотеках. Если библиотеки не использовать, то операции вы должны определить сами. А каким образом вы будете их определять - дело ваше, можете ознакомиться со статьей на википедии, которую я предоставил в предыдущем комменте, там уже представлены многие возможные алгоритмы.
И естественно, если вам не хватает стандартных типов, то что-бы обойти одно ограничение, придется ограничить себя в другом - в скорости! Длинная арифметика будет гораздо медленнее дефолтной, особенно это актуально для самописных велосипедов.

[Griboks]

x67: повторяю, я ничего не придумываю, перечитайте шапку. Я спрашиваю, как определить операцию умножения в c# для больших чисел. Пока что, не увидел решаемости этого.

[x67]

Griboks:

Я спрашиваю, как определить операцию умножения в c# для больших чисел. Пока что, не увидел решаемости этого

На этот вопрос я вам ответил. Неоднократно. Перечитайте комментарии.

Answer 3

[Владимир Олохтонов]

Быстрое преобразование Фурье позволит сделать это за О(nlogn).
https://m.habrahabr.ru/post/113642/