1
$\begingroup$

You have a few variables that can only assume the values 0 or 1 and you use those to form two polynomials. Is there a way to multiply the two polynomials that is faster than O(n²) where n is the number of terms in the polynomial?

What I could come up with:

  • As the variables are binary, they all follow the equation X²=X

  • You can represent any polynomial of this kind with an array of $2^n$ values, where n is the number of variables, where each index represents the variables multiplied and the value at the index position represents the quantity multiplied.

Example: for a polynomial with 3 variables, the array indexes will be as follows:
0 - _
1 - a
2 - b
3 - a * b
4 - c
5 - a * c
6 - b * c
7 - a * b * c

And the polynomial 1+3a-2b+bc could be represented as [1, 3, -2, 0, 0, 0, 1, 0]

  • to add two polynomials in this representation you just have to add the arrays

  • the value of the multiplication of two terms can be calculated multiplying their values and the index can be found by applying OR in their indexes. Example: array A and array B represents two distinct binary polynomials and K is the result of the multiplication. A[i] * B[j] -> K[i | j] = A[i] * B[j]

So, is there a faster way than looping and distributing each term?

$\endgroup$
6
  • $\begingroup$ Your representation requires an array of size $2^n$. It can be much more than the actual number of terms in the polynomial. $\endgroup$ – user114966 Mar 27 at 17:26
  • $\begingroup$ @Dmitry you are correct, thanks for pointing that out. It was a typo in the question. And while it can be much more than the actual polynomial, I can't think of a better representation than that for making the calculations $\endgroup$ – Victor Marcelino Mar 27 at 18:09
  • 2
    $\begingroup$ en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/… $\endgroup$ – D.W. Mar 27 at 19:32
  • $\begingroup$ Are your polynomials sparse or dense? How many variables are involved? $\endgroup$ – Yuval Filmus Mar 28 at 16:21
  • $\begingroup$ The answer could also depend on the representation that you use. For example, if you multiply $x_1 + \cdots + x_n$ by $y_1 + \cdots + y_n$ and you represent polynomials as sums of terms, then you cannot do better than $\Theta(n^2)$, since the resulting polynomial has $n^2$ terms. In fact, it could be worse if each monomial has high degree — your upper bound of $O(n^2)$ doesn't necessarily hold, depending on your model of computation. $\endgroup$ – Yuval Filmus Mar 28 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.