How to find the Number of Roots of a Polynomial in a Real Range Is there a way to efficiently find the number of real roots of a polynomial $P$ in a range $[a,b]$ with $a,b \in \mathbb{R}$? You may/may not know much about the coefficients of the polynomial, so I want methods that work based on the fact that it's a polynomial.
EDIT: I know about Sturm's theorem, but I think it would be too slow for my use case (polynomial of around degree 30), as I have to generate at most n polynomials, n being the degree of the original polynomial.
 A: Use Sturm's theorem.
For low degrees, one can frequently translate the variable $x \mapsto x -a$ and $x \mapsto x-b$, apply Descartes' rule of signs to each, and also get the desired result.
A: I am afraid there is no free lunch. The analytical expression of the number of real roots of a polynomial is precisely the one generated by the Sturm sequence, and no simplification has been found so far (AFAIK). So the direct method is Sturm's.
Other approaches (such as based on Descartes's rule) will require iterations, the number of which is unpredictable and worsens as the roots get closer to each other. (An efficient implementation can be obtained by converting the polynomial to the Bernstein basis and exploiting the "hull property" - if some coefficient differ in sign, there must be a zero. Then a dichotomic subdivision process is made efficient by De Casteljau's algorithm. https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/bezier-sub.html; https://pdfs.semanticscholar.org/e8db/366b5a403d67fd265b64b3c6e24fbf4e04cb.pdf)
In addition, I guess that for polynomials of degree 30, numerical instabilities will creep in.
