Mathematical background

Let a polynomial $P$ and define $f_0=P$, $f_1$ be the first derivative of $P$. Then define the sequence $f_i = -{\tt Rem}(f_{i-2},f_{i-1})$ where Rem is the remainder of the division of $f_{i-2}$ by $f_{i-1}$. If $n$ is the degree of $P$ the last element in the sequence will be $f_n$. Assume now that we are looking for the number of distinct roots of $P$ in the interval $[a,b]$ with $P(a)P(b)\not=0$. We build two sequences:

$$\{ f_0(a),f_1(a),\ldots,f_n(a)\}~~~\{ f_0(b),f_1(b),\ldots,f_n(b)\}~~~$$

Let $n_0$ be the number of change of sign in the first sequence and $n_1$ be the number of change of sign in the second sequence. Then the number of distinct real roots of $P$ in the interval $[a,b]$ is $n_0-n_1$ [14] if $f_0(a)f_0(b)\not =0$. Note that a multiple roots count only for one root with this method.

The drawback of Sturm method is that the absolute value of the coefficients increase quickly when computing the sequence. Numerical rounding errors may then affect the result. The alternate method of Budan-Fourier (see section 5.5.2) is less sensitive to rounding errors although it provides less information than Sturm method.