How to find the range of zeroes in a polynomial I am writing a java program that finds all of the zeroes of a polynomial by bisection. The first step, clearly, is to iterate through integers in a certain range looking for sign changes. I could simply use Integer.MIN_VAL and Integer.MAX_VAL for my range, but that seems horribly inefficient. Is there a method (preferably relatively simple to implement in a program) that can give me a better idea of what range to look in? Or am I out of luck? It needs to work on polynomials of any degree.
 A: Let $P = a_n x^n + \dots + a_0$.
You can find explicitly $\tilde x_{\max} = \sum_k (|a_k/a_n|)^{1/(n-k)}$, from which $a_n x^n$ dominates over $a_k x^k$. This gives you an upper bound for the absolute value of the largest root.
Fujiwara bound is $x_{\max} = \max ( |a_0/a_n|^{1/n} + 2\max_{n>k>0} |a_k/a_n|^{1/(n-k)})$, see http://www.sciencedirect.com/science/article/pii/S0377042703003819 and http://www.sciencedirect.com/science/article/pii/S0377042703009397
A: There are several bounds on the size of polynomial roots. Two of the easier ones are
$$
R=1+\max_{k=0,...,n-1}\left|\frac{a_k}{a_n}\right|
$$
and 
$$
R=\max\left(1,\frac{|a_0|+|a_1|+...+|a_{n-1}|}{|a_n|}\right).
$$
See also https://en.wikipedia.org/wiki/Properties_of_polynomial_roots#Bounds_on_.28complex.29_polynomial_roots
A: The bisection method, very useful from a logical point of view, as you have noticed, is terribly inefficient from a computational one.
There are several other methods, the most efficient I found for polynomials is the  Newton-Raphson one.
Given a function $f$, derivable on an interval, you guess $x_0$ is a root, if it's not you approximate the function linearly by the curve $y = f'(x_0)(x-x_0) + f(x_0)$ then find the $x_1$ where $y=0$ i.e. $x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$, try if $f(x_1)=0$. If $x_1$ is not a root reiterate the procedure til the precision desired.
