# Is there an efficient algorithm for evaluating a polynomial on the form $\prod_i(x_i+y_i) - \prod_i x_i$

I have an algebra that behaves very similarly to polynomials. A frequent occurrence there is multivariate polynomials on the form $\prod_i(x_i+y_i) - \prod_i x_i$. In this algebra subtraction is prohibitively expensive.

Are there any good algorithms for efficient computation of this kind of polynomial?

Define $P_i=(x_1+y_1)\dots(x_i+y_i)x_{i+1}\dots x_n$ for $0\leq i \leq n$, so we want to compute $$P_n-P_0 = (P_n-P_{n-1}) + (P_{n-1} - P_{n-2}) + \dots + (P_1 - P_0).$$
which can be computed as a sum of the differences $$P_i-P_{i-1}=(x_1+y_1)\dots(x_{i-1}+y_{i-1})y_ix_{i+1}\dots x_n.$$
• Wouldn't this miss the term $x_1*(x_2+y_2)*x_3$ for example? – Bomaz Sep 11 '17 at 13:24
• @Bomaz: $x_1(x_2+y_2)x_3$ includes the monomial $x_1x_2x_3$, which does not appear in your original polynomial – Dap Sep 11 '17 at 15:19