  Let f be a degree D univariate polynomial with real coefficients and exactly
m monomial terms. We show that in the special case m=3 we can approximate
within eps all the roots of f in the interval [0,R] using just
O(log(D)log(Dlog(R/eps))) arithmetic operations. In particular, we can count
the number of roots in any bounded interval using just O(log^2 D) arithmetic
operations. Our speed-ups are significant and near-optimal: The asymptotically
sharpest previous complexity upper bounds for both problems were super-linear
in D, while our algorithm has complexity close to the respective complexity
lower bounds. We also discuss conditions under which our algorithms can be
extended to general m, and a connection to a real analogue of Smale's 17th
Problem.
