Given two Gaussian integers $x$, $y$ what's the fastest way to find the Gaussian integer $z$ which minimizes $|x - zy|$? Then this Gaussian integer can be taken as $z = x/y$.
Algorithm to find nearest quotient in $\mathbb{Z}[i]$
1
$\begingroup$
number-theory
ring-theory
computer-science
-
2It should be noted that there may be two or even four Gaussian integers all of which minimize $|x-zy|$. – 2012-06-04
-
5I am not good on speed. But "simplify" by multiplying top and bottom by the conjugate of $y$. We obtain something of shape $s+it$ where $s$ and $t$ are rational. Let $a$ and $b$ be integers nearest to $s$ and $t$ respectively. (If $s$ and/or $t$ is half of an odd integer, we have more than one choice.) – 2012-06-04