I am looking for an algorithm to calculate the Square-root (cube-root?)of an Gaussian integer n, where n isn't a square number.
So i define the integer square root of an gaussian-integer n as the largest number r (with respect to the norm) with $r^2$ <= n.
With n = c+di I am looking for the number r = a+bi with maximal norm $q = a^2+b^2$ where $q^2 \leqslant c^2 + d^2$.
Using $(a+bi)^2 = a^2 - b^2 + 2ab i$ and $a^2+b^2 = \sqrt{c^2+d^2}$ I get the following three equations:
a) $a^2-b^2 = c$
b) $d = 2ab$
c) $a^2+b^2 = \sqrt{c^2+d^2}$
Adding a) and c) I get
a') $2a^2 = c + \sqrt{c^2+d^2}$
Solving for a and b I get something like
$a = \sqrt \frac{(c + \sqrt{c^2+d^2})}{2}, b = \frac{d}{2a}$ ,
I am looking for an algorithm to calculate this value only in integer operations. And the obvious generalization to cubic roots and Eisenstein integers.
Everything I tried is numerically unstable. Is there any general approach?