나는 3 일 동안 tis를 계산하려고 노력 해왔다. 다항식 곱셈 (곱하기 2 차 방정식)을 구현해야합니다. 그들은 다음과 같이 보입니다 :다항식 곱셈의 복잡도 감소
(a1 x^2 + b1 x + c1) * (a2 x^2 + b2 x + c2);
그러나 더 까다로운 부분은 5 계수 멀티 플리케이션에서 구현하는 것입니다. 예를 들어, a1 * b1, (a1 + a2) * (b1 + b2)는 하나의 곱셈으로 간주됩니다. 그러나 (a1 x + a2) * (b1 x + b2)는 4로 계산됩니다 (a1 b1, a1 b2, a2 b1, a2 b2).
당신은 multiprecision 곱셈에 사용되는 TOOM-3 알고리즘을 좀보고 할 수 있습니다. Ref : Toom-Cook multiplication.
기본적으로 추가 및 쉬프트 만 사용하여 x = -2, -1,0, + 1, 무한대의 각 다항식을 계산 한 다음이 5 개의 값을 곱하여 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하고, 값은 다음과 같습니다 : 값 X = -2, -1,0에서 P(X) = A*X^2 + B*X + C를 들어
, + 1, 무한대은
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
당신은 알고있다 x = -2, -1,0, + 1, 무한대의 값은 R(x) = P(x)*Q(x)이고 계수 T, U, V, W, K를 얻으려면이 선형 시스템을 풀어야합니다.
고맙습니다. 나는 3 일 동안 잠못 들었다. – Brahadeesh
흠 나는 대답을 찾은 것 같습니다.
(x * (A1 * x + b1) + c1) * (x * (a2 * x + b2) + c2)로 바꿉니다.
그리고 거기에 5 개의 곱셈이 있습니다.
죄송합니다. 죄송합니다. 첫 번째 답변이 잘못되어 9 회의 곱셈이 실제로 발생했습니다.
나는 그가 9 번의 곱셈으로 계산한다고 생각한다. – ThomasMcLeod
예 9 곱셈입니다. 내가 지정하기를 원한다면, 나는 그것을 할 것이다. 그러나 그 꽤 명백한. – Brahadeesh
@Brahadeesh 전혀 분명하지 않습니다. 이 수식에는 5 개의 곱셈이 있습니다. 당신은 최적이라고 질문했지만, 방정식을 확장하는 것이 좋습니다. 그것은 차선책 인 무언가를 원할 때 당신이하는 일입니다. –
나는 또한 자신이나 다른 사람들이 풀 수있는 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
게시 해 주셔서 감사합니다. 나는 똑같은 해결책을 가지고 있었다. – Brahadeesh
환급액을 6 일 곱셈으로 게시 할 수 있습니까? – threenplusone