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

## 2 Answers

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

• Can you expand on that "not guaranteed to work"? Are there known cases where it fails?
– G_B
Commented Jul 1, 2022 at 0:13
• I don’t have an example for triplets. But take $x=1{.}3247 \cdots$ a root of $x^3-x-1$. Then starting from the quintuple $(1, x, x^2, x^3, x^4)$ this procedure will never reach zero and so it fails to find an integer relation, even though it clearly exists.
– WimC
Commented Jul 1, 2022 at 5:01
• For a triplet, I think one could take $x=1.4656...$, as a root of $x^3-x^2-1$? That guarantees that each succeeding triplet will still be in the same ratio $1:x:x^2$, converging to zero without ever reaching it. But both these examples violate the problem's assumption that $x$ is the solution to a quadratic, so they don't disqualify this method.
– G_B
Commented Jul 1, 2022 at 22:39
• Indeed. And in this case there is no integer relation between $(1,x,x^2)$ since $x^3-x^2-1$ is irreducible. Also note that in the example of $x^3-x-1$, starting with the quadruple $(1,x,x^2,x^3)$ does find the relation. So, now we both have something to think about. :-)
– WimC
Commented Jul 2, 2022 at 5:05

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

• How would you realize when you’ve hit the periodic part of the sequence? Would it be possible that you see repeated values without having seen the start/end of the period? Commented Jun 30, 2022 at 5:40
• @templatetypedef Looking only at the first $n$ values of the sequence it'll never be possible to tell for sure between something that's hit periodicity and something that only looks periodic, but if you're saving the fractional parts at each stage you can test that by checking whether those are equal. The challenge then would be finding a strategy that picks up periodicity quickly without needing to store too many fraction values or do too many comparisons.
– G_B
Commented Jun 30, 2022 at 6:45
• Thanks, I will wait the customary 24 hours, but this looks good. Evidently I am rustier than I realised on continued fractions!
– G_B
Commented Jun 30, 2022 at 6:47
• I liked both these answers just about equally but for different reasons. Yours is a little closer to the kind of approach I had in mind, WimC's has the advantage of a finite termination which avoids the need to identify when the series repeats. I would have accepted both if I could, in the end I had to toss a coin.
– G_B
Commented Jul 4, 2022 at 23:51