I have a method for dividing polynomials with remainder. It works well for polynomials whose coefficients are precisely divided. But when trying to divide, for example 2*x^3-18*x^2+.... at 7.00000(много нулей)0000028*x^2 + 5*x + ... there is a problem. First of all, the coefficients for the higher terms are divided: 2*x^3 / 7.000...000028*x^2 . We 0.285714....53*x . Then it is necessary to multiply the obtained value of 0.2857....53*x by the divisor 7.00000...0000028*x^2 + 5*x + .. and subtract 2*x^3-18*x^2+... from the divisible polynomial . So we get the remainder of degree 2. But due to problems with the accuracy of the calculations, after subtraction I get not a polynomial of degree 2, but this is 2.220....E-16*x^3 - 6*x^2 + .... It is clear that in fact there is almost zero near x^3 , but due to the fact that this is not the case, the algorithm loops. How to solve this problem in order not to reinvent the wheel?

    3 answers 3

    You simply always subtract the highest degree completely! Why then multiply again?

     (ax^3+bx^2+cx+d) / (ex^2+fx+g) => // первый член - ax/e

    Residue: (bx^2+cx+d - (afx^2/e+agx/e)) , then divide it further ...
    When the term x^3 coefficient is by definition zero!

    More or less clear? terribly do not want to build it all in TeX'e ...

    • Yes, I understand what you mean. I think that's what I'll do, Thank you! - danielleontiev

    You did not specify any code that would help solve the problem, because it depends on how you compare double numbers. I guess how you do it, and therefore I suggest doing the following after the calculations made. If a certain number in absolute value is less than the predetermined accuracy, for example, const double EPS = 1e-8 , then we intentionally make this number equal to zero. Something like that:

     if (abs(a) < EPS) a = 0.0;

    If there was a code, I would specifically show where and how to do it, but I think you already understood that.

      Rewrite algorithm It should only determine the degree of the polynomial once, and then work in such a way that only the array suffix is ​​processed at each iteration. Well, it is necessary to compare with zero with some accuracy, as written in other answers.

      • This is more like a comment than an answer. "When your reputation reaches the blah blah blah you can leave comments." ;) Okay, the question itself without a code - so let it remain. - AK ♦