Sharma’s algorithm for finding the list of isolating intervals for the roots of a square-free polynomial (with real coefficients) uses a Möbius transformation, which in turn can be associated with a finite continued fraction. Moreover, Sharma proves that this algorithm has a complexity of at worst Õ(n7L2), where Õ means that he has neglected logarithmic factors, n is the degree of the polynomial, and L is the bit length. The proof of this claim makes use of some proven theorems concerning continued fractions, including those related to the Fibonacci numbers.
Some minor typographical errors do not impair the clarity of the paper, since the correct meaning can be grasped from the context. For example, on page 343, the paragraph just above Equation 11 states: “this implies that Qi ≥ &phgr; i, where &phgr; =(1+√5)/2”. Clearly, it should instead use Qm and &phgr;m--only the last Fibonacci fraction converges to the golden number, as implied. Also, above Lemma 3.1, the symbol ≥ 0 is written as a subindex, when it should be next to the symbol of real numbers.
This paper does not merely state the algorithmic complexity for finding roots, but also provides some insight for future improvement. Consequently, I recommend this paper to computer algebra developers, and to those mathematicians seeking to write their own codes for faster calculations of real roots.