Complexity of computation on real algebraic numbers (Q757065): Difference between revisions

Improving on earlier results a new and more efficient algorithm for coding real algebraic numbers is proposed. First, given finitely many polynomials \(P,Q_ 1,...,Q_ k\in {\mathbb{Z}}[X]\) and sign conditions \(\epsilon_ 1,...,\epsilon_ k\in \{-1,0,+1\}\) an algorithm is developed to count the real roots \(\alpha\) of P with side conditions \(Q_ i(\alpha)<0\), \(=0\) or \(>0\) according as \(\epsilon_ i=-1\), \(=0\) or \(=+1.\) Then this is applied to P and all of its derivatives \(P^{(1)},...,P^{(k)}\) (if \(\deg (P)=k)\). It is known that the root \(\alpha\) of P is uniquely determined by the signs of \(P^{(k)}(\alpha),...,P^{(1)}(\alpha)\) computed in this order. The increased efficiency of the new algorithm depends on the fact that usually not all of these signs have to be computed. The first algorithm can be used to determine when the computation may be stopped.