Я пытался понять это в течение 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).
Вы можете взглянуть на алгоритм 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.
Хм, кажется, я нашел ответ.
вы заменяете его на ( x * ( A1 * x + b1 ) + c1 ) * ( x * ( a2 * x + b2 ) + c2 );
и там у вас есть 5 умножений.
Извините, это было отредактировано, мой первый ответ был неправильным и действительно имел 9 умножений.
Я также нашел решение для умножения на 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
