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.

  • $\begingroup$ What is your definition of a significant coefficient? How is counting the number of significant coefficients different from counting the number of coefficients? $\endgroup$ – D.W. Aug 29 '13 at 7:30
  • $\begingroup$ @D.W. I meant non-trivial coefficients $\endgroup$ – SadStudent Aug 29 '13 at 8:31

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.

| cite | improve this answer | |
  • $\begingroup$ but when you say "you can first run a loop that checks how many non-zero terms the result has", id does mean calculating the result twice , doesn't it? $\endgroup$ – SadStudent Aug 28 '13 at 21:43
  • $\begingroup$ As I mention, the first loop could be faster in principle (say if the magnitudes of the coefficient are very different), and in any case it only requires constant space. $\endgroup$ – Yuval Filmus Aug 28 '13 at 22:07

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.