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.
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$.