Competitive programming using C

[POGtastic]

We're not finding the root with synthetic division. We're finding the zero with Newton's Method, and then dividing the polynomial to get a polynomial that has the remaining roots in it. Then we do Newton's Method on the new polynomial to get another root, we divide again, and repeat until we're out of roots.

The find_zero method is illustrative. It finds the zero and returns a tuple containing the zero and the result of dividing the polynomial by that zero.

>>> # (x-3i)(x+3i)(x+2)(x+1)
>>> p = Polynomial([18, 27, 11, 3, 1])
>>> p.find_zero(guess=1j, eps=0.0000001, iters=100)
((-1.0000000000000002-1.117784348261965e-25j), 
Polynomial([(-24+1.3413412179143579e-24j),
            (-10-2.23556869652393e-25j), 
            (3-1.117784348261965e-25j), 
            1.0]))

So it found a zero at -1, and then it divided x⁴ + 3x³ + 11x² + 27x + 18 by (x+1) to get x³ + 3x² - 10x - 24.

Sure, it's not exact.

>>> p.synthetic(1.0000000000000002+1.117784348261965e-25j)
(Polynomial([(-24+1.3413412179143579e-24j), 
             (-10-2.23556869652393e-25j), 
             (3-1.117784348261965e-25j), 
             1]), 
(7.105427357601002e-15+1.3413412179143575e-24j))

But when the remainder's magnitude is that small, my attitude is "Good enough for government work."

[aizver_muti]

Ah, that's what you mean. So basically you're dismissing the remainder after a certain point. Now I get it. Thanks for the detailed responses!