1
$\begingroup$

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

  • 5
    I 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

1 Answers 1

1

This is essentially a rewrite of the comment from @AndréNicolas. Multiply by the conjugate $\bar y$ of $y$, then the problem becomes to minimize $\left|x\bar y - z\Vert y \Vert^2\right|$ where $\Vert y\Vert^2$ is an integer. So $z=\mathrm{round}\left(\mathrm{Re}(x\bar y)/\Vert y \Vert^2\right)+i\cdot\mathrm{round}\left(\mathrm{Im}(x\bar y)/\Vert y \Vert^2\right)$ solves the problem (and, as commented, can have multiple possibilities depending on how you round halves).