Calculate the number of elements after multiplying/adding two polynomials

Question

Suppose I have two polynomials $f(x)$ and $g(x)$ and I somehow represent their coefficients. I have a couple of ways to hold a polynomial depending on how many significant coefficients the polynomial has. I want to determine the amount of significant coefficients in the results of $f(x) + g(x)$ ,$f(x) \cdot g(x)$ , $f(x) - g(x)$ etc. .

But I'd like to do it before I create the object that holds them, is there some efficient way of doing this without calculating the result twice?

I can assume that I know the current rank and number of elements in $f(x)$ and $g(x)$

If this is not possible knowing that the new polynomial's non-trivial coefficients will be at least half of the rank will suffice, but I'm unsure how to do it as well.

I did try to apply various heuristics but didn't come up with something consistent and fast.

Answer 1

If $F$ is the number of terms in $f(x)$ and $G$ is the number of terms in $g(x)$ then the number of terms in $f(x)\pm g(x)$ is between $|F-G|$ and $F+G$, and all cases can occur. If you want to calculate the number of terms, you can first run a loop that checks how many non-zero terms the result has, allocate the needed array, and then do the actual computation. The first pass could be faster, since you are only comparing coefficients, which might be faster than actually adding or subtracting them.

For $f(x) \cdot g(x)$, the number of terms is between $F+G-1$ and $FG$, and again these extreme cases can actually occur. Again you can run a first pass which calculates how many non-zero terms there are, though you'd have to be careful if you want to implement it using constant space and the same time (if it is at all possible). It might be better to calculate the product and then reallocate the result to its actual size.