You have a mistake in Monomial where you encode the coefficient as an int. This will strip non-integer information from the double....

Are you forced to base polynomial on monomials? really all you need to store an arbitrary polynomial is a variable length array for the coefficient values where the exponent is implied by the index... now for sparse polynomials (where coeff is non-zero for a small number entries) then this would be inefficient. You could still use the monomial in this solution. You just have it in an array and you are explicitly storing the coefficient.

The next alternative is to store the monomials in a list. The poly is evaluated simply by running down the list and summing the results. adding poly's can be done just by appending the mono's to the list. Mult is similar, mult the mono's and append the to the list. The danger there is this list is not sensitive to the exponent, so it may have many entries at the same exponent. This is costly for memory and computation...

So then the next improvement is force the mono's to be stored in a structure that ensure you have a unique exponent. std::set does that.... (std::map is another except you end up storing the exponent twice once in the key and again in the monomial). With std::set you will have to define a comparison to have it sort on the coefficient.... read the doc's on that. In the implementation you just need some extra care to ensure results are either inserted or added depending on whether that coefficient exists or not... there are other things you can do for efficiency. Keep in mind you cannot modify entries in the std::set but there are ways around that.

So there you have it... you have a couple options.... hope that helps....

Are you forced to base polynomial on monomials? really all you need to store an arbitrary polynomial is a variable length array for the coefficient values where the exponent is implied by the index... now for sparse polynomials (where coeff is non-zero for a small number entries) then this would be inefficient. You could still use the monomial in this solution. You just have it in an array and you are explicitly storing the coefficient.

The next alternative is to store the monomials in a list. The poly is evaluated simply by running down the list and summing the results. adding poly's can be done just by appending the mono's to the list. Mult is similar, mult the mono's and append the to the list. The danger there is this list is not sensitive to the exponent, so it may have many entries at the same exponent. This is costly for memory and computation...

So then the next improvement is force the mono's to be stored in a structure that ensure you have a unique exponent. std::set does that.... (std::map is another except you end up storing the exponent twice once in the key and again in the monomial). With std::set you will have to define a comparison to have it sort on the coefficient.... read the doc's on that. In the implementation you just need some extra care to ensure results are either inserted or added depending on whether that coefficient exists or not... there are other things you can do for efficiency. Keep in mind you cannot modify entries in the std::set but there are ways around that.

So there you have it... you have a couple options.... hope that helps....

Last edited on

Topic archived. No new replies allowed.