Algorithm to convert a real to surd representation? Supposing I'm given an infinite-precision calculator containing a number $x$, which I know to be the ratio of two coprime integers $p$, $q$, with $q > 0$, and I want to find out what those integers are.
The Euclidean algorithm allows us to do this in $O(\log(\min(p,q)))$ steps:

*

*Subtract the integer part of $x$, making a note of what it was

*Take the reciprocal of the remaining fractional part

*Repeat until we get an integer

*Use the integer parts determined above to represent $x$ as a continued fraction of finite length, from which we can easily find values of $p, q$.

But if we are instead given $x = p+\sqrt{q}$ or perhaps $x = \frac{p+\sqrt{q}}{r}$, for some unknown $p, q, r$ integers, is there a comparable algorithm for finding their values?
Obviously since the set of such numbers is countable we could simply iterate through $p, q, r$ until we find a solution, and for the first case we'd simply need to iterate through integer $n$ testing whether $(x-n)^2$ is integer. But I'm interested in whether there are more elegant/efficient methods.
 A: You can do exactly the same. The quadratic numbers are exactly the numbers that have an (eventually) periodic continued fraction expansion. So, you keep calculating the continued fraction expansion until you're left with a number that you've seen before and from the resulting periodic continued fraction expansion you can compute $p$, $q$, and $r$.
(This does require that your infinite-precision calculator can determine equality between two infinite precision numbers, but that's comparable to it being able to see if an infinite precision number is actually an integer.)
A: Find an integer relation between the numbers $1, x, x^2$. This gives a quadratic equation for $x$ with integer coefficients and hence an expression for $x$ as requested. An algorithm like PSLQ finds such a relation if it exists (if precision is not a limiting factor). However. There is a much simpler algorithm that is not guaranteed to work, but does work well in practice. (For example, it finds the spigot relation for $\pi$ that boosted PSLQ’s fame without any issue.) It is a variation on the Euclidean algorithm where you repeatedly reduce the largest number by taking the remainder mod the second largest number, until you hit zero.
As a simple example, consider the number $x = \sqrt{2} + 1$.  Starting at the numbers $1, x, x^2$ and performing repeated reduction of the largest two values, you find the following ordered triples:
$$(1,x,x^2), (1, 1, x), (x - 2, 1, 1), (0, x - 2, 1)$$
which leads to the relation $-1-2x+x^2 = 0$.
