Уменьшение сложности полиномиального умножения

Question

Я пытался понять это в течение 3 дней и нигде не получил.Я должен реализовать полиномиальное умножение (умножить 2 квадратных уравнения).Они выглядят так:

( a1 x^2 + b1 x + c1 ) * ( a2 x^2 + b2 x + c2 );

Но самое сложное - реализовать его в 5-кратном умножении.Я уменьшил его до 6. Например, a1 * b1, (a1 + a2) * (b1 + b2) считаются одним умножением.Но (a1 x + a2) * (b1 x + b2) считается как 4 (a1 b1, a1 b2, a2 ​​b1, a2 b2).

Answer 1

Возможно, вы захотите взглянуть на алгоритм Toom-3, используемый при многократном умножении.Ссылка: Умножение Toom-Cook .

По существу, вы оцениваете каждый многочлен в x = -2, -1,0, + 1, бесконечность, используя только добавления и сдвиги, затем умножаете эти 5 значений, чтобы получить значения продукта при x = -2, -1,0, + 1, бесконечность.Последний шаг - возврат к коэффициентам результата.

Для P(X) = A*X^2 + B*X + C значения при x = -2, -1,0, + 1, бесконечность:

P(-2) = 4*A - 2*B + C  (the products here are bit shifts)
P(-1) = A - B + C
P( 0) = C
P(+1) = A + B + C
P(oo) = A

Произведение R(X) = T*X^4 + U*X^3 + V*X^2 + W*X + K и значения:

R(-2) = 16*T - 8*U + 4*V - 2*W + K
R(-1) = T - U + V - W + K
R( 0) = K
R(+1) = T + U + V + W + K
R(oo) = T

Вы знаете значения R(x) = P(x)*Q(x) для x = -2, -1,0, + 1, бесконечность, и вам нужно решитьэта линейная система для получения коэффициентов T, U, V, W, K.

Answer 2

Хм, кажется, я нашел ответ.

вы заменяете его на (x * (A1 * x + b1) + c1) * (x * (a2 * x + b2) + c2);

и вот вам 5 умножений.

Извините, это было отредактировано, мой первый ответ был неверным и действительно имел 9 умножений.

Answer 3

Я также нашел решение для умножения 6, которое могло бы помочь вам или другим решить.

M1 := (a1 + b1)*(a2 + b2)  
M2 := (a1 + c1)*(a2 + c2)  
M3 := (b1 + c1)*(b2 + c2)  
M4 := a1 * a2  
M5 := b1 * b2  
M6 := c1 * c2

Тогда это дает:

M4 * x^4 + 
(M1 - M4 - M5) * x^3 + 
(M2 - M4 - M6 + M5) * x^2 +
(M3 - M5 - M6) * x +
M6