I am trying to solve problem “POLYNOMIAL EQUATIONS” at SPOJ.I am not able to understand the algorithm behind this problem.If someone can help me in this i will be very grateful.
Thanks.
Problem Link:
Thanx for the link.
In this case, we could iterate over all possible x from -100 to 100 withb a step of 0.01, find F(x) and say that it’s a root if F(x) is close to zero (possibly with some higher-order corrections); for multiple roots, use the fact that k-times multiple root is a root of the (k-1)-th derivative. 
But this is how I’d do it: using Newton’s method (if f(x) is the derivative of F(x), start at arbitrary x, and iterate x -=F(x)/f(x) until F(x) is close to zero; it can fail for polynomials with complex roots, but we don’t have that here) find one root, call it r; we have a new polynomial G(x)=F(x)/(x-r) and the roots of F are r and roots of G. Newton converges really quickly!
1 Like
In this question , Since degree is bet 0 to 6 , you can directly apply the formula for all this 6 degrees directly .
3 Likes
The motive of asking this question was to solve it for polynomial of any degree.Anyways thanx for answering.
Thanx.I will try this.
Try Newton Raphson method which starts with an approx root and recursively converges to the result. It is very easy to implement also. As it is stated that precision should be 0.01 so 10 recursions are enough for a single root.
This is what the Newton Raphson method states if f(x) is the polynomial function then root of equation f(x)=0 can be calculated as x(n+1)=x(n)-f(x(n))/f’(x(n)).
Now start with the approximation with -100 and run upto 100 and keep storing roots in a array and finally output all the distinct roots. (Here by distinct we mean roots with difference more than 0.01)
We can assume that the method takes constant time to arrive at an good approximation. Hence the complexity is of O(range of roots).
Hope this helps. 