<s>[INST] Algorithm to decide whether two constructible numbers are equal? The set of constructible numbers 
https://en.wikipedia.org/wiki/Constructible_number
is the smallest field extension of $\mathbb{Q}$ that is closed under square root and complex conjugation. I am looking for an algorithm that decides if two constructible numbers are equal (or, what is the same, if a constructible number is zero). 
As equality of rational numbers is trivial, this algorithm probably needs to reduce the complexity of the involved number in several steps.
Does such an algorithm exist? If yes, what does it look like?
 [/INST] Although this can be done using the complicated algorithms for general algebraic numbers, there’s a much simpler recursive algorithm for constructible numbers that I implemented in the Haskell constructible library.
A constructible field extension is either $\mathbb Q$ or $F{\left[\sqrt r\right]}$ for some simpler constructible field extension $F$ and $r ∈ F$ with $\sqrt r ∉ F$.  We represent an element of $F{\left[\sqrt r\right]}$ as $a + b\sqrt r$ with $a, b ∈ F$.  We have these obvious rules for $a, b, c, d ∈ F$:
$$\begin{gather*}
(a + b\sqrt r) + (c + d\sqrt r) = (a + c) + (b + d)\sqrt r, \\
-(a + b\sqrt r) = -a + (-b)\sqrt r, \\
(a + b\sqrt r)(c + d\sqrt r) = (ac + bdr) + (ad + bc)\sqrt r, \\
\frac{a + b\sqrt r}{c + d\sqrt r} = \frac{ac - bdr}{c^2 - d^2 r} + \frac{bc - ad}{c^2 - d^2 r}\sqrt r, \\
a + b\sqrt r = c + d\sqrt r \iff a = c ∧ b = d.
\end{gather*}$$
To compute the square root of $a + b\sqrt r ∈ F{\left[\sqrt r\right]}$:

*

*If $\sqrt{a^2 - b^2 r} ∈ F$ and $\sqrt{\frac{a + \sqrt{a^2 - b^2 r}}{2}} ∈ F$, then
$$\sqrt{a + b\sqrt r} = \sqrt{\frac{a + \sqrt{a^2 - b^2 r}}{2}} + \frac{b}{2\sqrt{\frac{a + \sqrt{a^2 - b^2 r}}{2}}}\sqrt r ∈ F{\left[\sqrt r\right]}.$$

*If $\sqrt{a^2 - b^2 r} ∈ F$ and $\sqrt{\frac{a + \sqrt{a^2 - b^2 r}}{2r}} ∈ F$, then
$$\sqrt{a + b\sqrt r} = \frac{b}{2\sqrt{\frac{a + \sqrt{a^2 - b^2 r}}{2r}}} + \sqrt{\frac{a + \sqrt{a^2 - b^2 r}}{2r}}\sqrt r ∈ F{\left[\sqrt r\right]}.$$

*Otherwise, $\sqrt{a + b\sqrt r} ∉ F{\left[\sqrt r\right]}$, so we represent it as
$$0 + 1\sqrt{a + b\sqrt r} ∈ F{\left[\sqrt r\right]}\left[\sqrt{a + b\sqrt r}\right].$$
In order to compute with numbers represented in different field extensions, we need to rewrite them in a common field extension first.  To rewrite $a + b\sqrt r ∈ F{\left[\sqrt r\right]}$ and $c ∈ G$ in a common field extension, first rewrite $a, b, r ∈ F$ and $c ∈ G$ in a common field extension $H$.  If $\sqrt r ∈ H$, then we have $a + b\sqrt r, c ∈ H$; otherwise we have $a + b\sqrt r, c + 0\sqrt r ∈ H{\left[\sqrt r\right]}$.
I implemented the constructible real numbers and built the constructible complex numbers generically on top of those, to enable ordering relations and to avoid having to think too hard about branch cuts.
</s>