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.
