Блог

Многочлены обычно записываются в виде суммы степеней (или различных произведений генераторов), и Google дает мне множество результатов, как перейти от этого к форме, которая является произведением чистых сумм (той, где вы можете видеть, где полином исчезает).:

x^2 — 1 = (x 1) (x — 1)

Однако я ищу другое направление, которое намного проще, но все равно дорого с точки зрения вычислений, если делать это наивно.

У меня есть массив из n значений, на которых полином обращается в нуль. Могу ли я каким-то образом получить коэффициенты в n log n?

Я в этом сомневаюсь. N log N — теоретически известная наилучшая асимптотическая скорость для умножения полиномов. Однако проблема, по-видимому, требует иерархического полиномиального расширения путем умножения

 step 1) x^2   Ax   B = (x   a)(x   b), x^2   Cx   D = (x   c)(x   d), ..., 
step 2) x^4   Ax^3   Bx^2   Cx   D = (x^2   Ax   B)(x^2   Cx   D), ...
...
step log N/2)  (polynomial of order N/2) * (polynomial of order N/2)
 

Когда размер полинома становится достаточно большим, можно начать использовать метод, основанный на БПФ, или Карацубу до этого. Я ожидал бы, что этот метод находится где-то между наивным методом O(N^2), который будет умножать базовый многочлен (x a) один на один с (x b), (x c)… и N log N, возможно, до N (log N)^2.