Book of programming problems

Complexity (1-100): 30

Solve the polynomial equation in real numbers:


where a_i are given real numbers. Print a message if there is no solutions.

A monotonous function can be solved by a simple binary division method. We can detect monotonous regions of the polynomial function P(x) by solving its derivative P'(x)=0 recursively. We can do that because the power of the derivative is less the the power of P(x) by one. The roots of this equation will be the local extremums, and P(x) in between the extremums is monotonous.

The figure shows the graph of function P(x)=2.5-x-2.5*x²+x³ and two roots a₀ and a₁ of the derivative equation P'(x)=-1-5*x+3*x²=0. We can check that the values P(a₀) and P(a₁) are of different sign, so there must by a root between a₀ and a₁. As the function is monotonous in this range, we can apply the binary division method.