So I want to make a system for computing with various classes of numbers. One of those is a class of number closed under the standard arithmetic operators ($+$, $-$, $\*$ and $/$) along with square roots. This is pretty simple: I can extend any sufficiently nice ordered ring $R$ into $R[X]/(X^2-K)$. How to calculate the standard arithmetic operators on this ring is well-known, and I found a very elegant algorithm for computing the order:


Take $f(x) = x\cdot\!\!\left|x\right|$. Suppose you want to know if $a+b\sqrt{K}<c+d\sqrt{K}$. With simple algebra we can change this question to $a-c<(d-b)\sqrt{K}$. If we apply $f$, we get $f(a-c)<f(d-b)\cdot K$. This reduces the inequality in $R[X]/(X^2-K)$ to an inequality in $R$. Thus, if we take $R$ to be some ring that we already have an algorithm for computing $<$ (such as $\mathbb{Z}$), we have a way of computing $<$ in $R[X]/(X^2-K)$.


This is all well and good. However, this only gives us square roots, and I would like as powerful of a system as possible. Even cube roots seem impossible to work with. Initially, they might seem easy, but one has to remember that members of $R[X]/(X^3-K)$ are of the form $a+b\sqrt[3]{K}+c\sqrt[3]{K}^2$, not $a+b\sqrt[3]{K}$. Thus, the 'easiest' question is this: can this method be extended to work with $n$'th roots? A harder question lies in extending this method to deal with roots of polynomials that are not of the form $x^n-k$, such as the polynomial $x^5-x-1$ (thus letting me compute nicely with real algebraic numbers).



Can this way of comparing numbers of the form a+b sqrt(K) be generalized?
Yes, you can compute with roots of arbitrary polynomials in a real-closed field. The algorithms are nowhere near as simple to describe, but in one way or another they can be thought of as generalizing the trivial algorithms for computing in $R[\sqrt K]$. See e.g. Yap, [Fundamental problems in algorithmic algebra](http://cs.nyu.edu/~yap/book/alge/ftpSite/) (in particular §VII), or Basu, Pollack, Roy, [Algorithms in Real Algebraic Geometry](http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted1.html) (§10).


Let me sketch some possibilities for the setup specifically mentioned in the question: we have a fixed ordered field $R$ where we know how to compute, an ordered algebraic extension $R[\alpha]$ of $R$, and we want to compute the ordering on elements of $R[\alpha]$; in other words, given a polynomial $f\in R[x]$, determine the sign of $f(\alpha)$.


First, there are several useful ways how to specify $\alpha$. One thing we want is an irreducible (or at least square-free) polynomial $g\in R[\alpha]$ such that $g(\alpha)=0$. Then we need something to uniquely determine $\alpha$ among the roots of $g$ in the real closure $\def\rcl#1{\tilde{#1}^\mathrm{real}}\rcl R$:


* The isolating interval representation consists of $u,v\in R\cup\{\pm\infty\}$ such that $\alpha$ is the unique root of $g$ in the interval $(u,v)$ of $\rcl R$. (Such an interval does not necessarily exist if $R$ is nonarchimedean.)
* The sign encoding consists of the sequence of signs of $g'(\alpha),g''(\alpha),\dots,g^{(d)}(\alpha)$, $d=\deg(g)$.
* Generalizing these two cases, we may be given a sequence of polynomials $h\_1,\dots,h\_k\in R[x]$ such that $\alpha$ is the unique root of $g$ in $\rcl R$ such that $h\_1(\alpha),\dots,h\_k(\alpha)>0$.


For example, for $\alpha=\sqrt[n]a$, we can take $g(x)=x^n-a$, and the isolating interval $(0,+\infty)$, or the sign encoding $(+,\dots,+)$, or $h\_1(x)=x$.


Now, assume we want to determine the sign of $f(\alpha)$:


* If $\alpha$ is given by an isolating interval $(u,v)$, and $f$ is square-free (which we can arrange by first computing its square-free decomposition), we can compute the Sturm sequence $f\_0=g$, $f\_1=f$, $f\_{i+1}=-(f\_{i-1}\bmod f\_i)$. Then the sign of $f(\alpha)$ is the sign of $(g(v)-g(u))(V(u)-V(v))$, where $V(u)$ is the number of sign changes (ignoring $0$) in the sequence $f\_0(u),f\_1(u),\dots$.
* If $\alpha$ is given by a sign encoding, or the more general representation with $h\_1,\dots,h\_k$: we run the BKR algorithm (see Yap, §VII.7–8) with $A=g$, $\overline B=[f,h\_1,\dots,h\_k]$. This will output all sequences of signs $[s,s\_1,\dots,s\_k]$ of $\overline B$ on the roots of $g$; one of them will be $[s,+,\dots,+]$, where $s$ is the sign of $f(\alpha)$.


