3
$\begingroup$

I was wondering:

I'm desiring to compute the following polynomial, $X_1^2 + 2 X_1\cdot X_2 +X_2^2$ where $X_1,X_2$ are indeterminates. I can store intermediate results and use the binary operators of multiplication and addition on the indeterminates.

If the cost of taking a scalar multiple is $0$, and the cost of using addition and multiplication is $1$, then consider the following:

Let $P=X_1+X_2$ (cost $1$). Let $Q=P \cdot P$ (cost $1$).

Now at this point $Q$ is $(X1+X2) \cdot (X1+X2)$. Am I allowed to be done with the computation at this point? Or must I end with the explicit $X_1^2+ 2 X1 \cdot X2 +X_2^2$ in order to have computed $X_1^2+2X_1 \cdot X_2+ X_2^2$? (Which would take $5$ steps).

  • 0
    Sorry, I was a bit tired last night and couldn't find the answer to this anywhere. Anyways yes, I mean you can perform multiplication and addition on the values taken on by the indeterminates. And you answered my question. Thanks!2011-08-23

1 Answers 1

2

Since you said my comment answered your question, I'm turning it into an answer so the question can be marked as answered:

If multiplication and addition refer to the values taken by the indeterminates, then $(X_1+X_2)\cdot(X_1+X_2)$ is the same as $X_1^2+2X_1\cdot X_2+X_2^2$, so there's nothing left to do; the computation was carried out efficiently with cost $2$ instead of cost $5$.

(By the way, under this interpretation of the question, presumably the coefficients of the polynomials are considered to be taken from some (relatively simple) subset of the possible values of the indeterminates? Else it wouldn't make sense to have scalar multiplication cost 0 and indeterminate multiplication cost 1, since they'd be the same operation.)