I've seen that $\mathbb{Z}[\varphi ] = \mathcal{O}_{\mathbb{Q}_{\sqrt{5}}}$, where $\varphi$ is the golden ratio, is a Euclidean domain with norm $N(x + y\varphi ) = x^{2} + xy - y^{2}$.
Given a particular $a, b\in\mathbb{Z}[\varphi ], b \neq 0$, I want an algorithm(that can be written in code) to find $q, r \in \mathbb{Z}[\varphi ]$ such that $a = qb + r, \; |N(b)|>|N(r)$| or $r = 0$.
Here's what I've come up with so far. If $b = c + d\varphi$, then let $b' = (c+d)-d\varphi$. It can be shown that $bb' = N(b)$.
If we set $q_{0} = ab'/N(b)$ then we have $a = bq_{0}$, but we have no guarantee that $q_{0}$ is in $\mathbb{Z}[\varphi ]$. We need some way of 'rounding' $q_{0}$ to get $q\in\mathbb{Z}[\varphi ]$ so a suitable $r$ falls out. It's this 'rounding' that I don't know how to execute.
We let $\phi={1+\sqrt5\over2}$.
Given $a,b$ in ${\bf Z}[\phi]$, $b\ne0$, we let $$a/b=q_0= ab'/N(b)=s+t\phi$$ with $s,t$ rational and $b'$ defined as above. We choose integers $u,v$ with $$|s-u|\le1/2{\rm\ and\ }|t-v|\le1/2$$ We let $q=u+v\phi$, so $q\in{\bf Z}[\phi]$, and let $r=a-bq$, so also $r\in{\bf Z}[\phi]$. Also, $$r=a-bq_0+b(q_0-q)=b\bigl((s-u)+(t-v)\phi\bigr)$$Then writing $N$ for the norm we have $$|N(r)|=|N(b)|\bigl|\bigl((s-u)^2+(s-u)(t-v)-(t-v)^2\bigr)\bigr|\le(1/2)|N(b)|$$ (using the trivial estimate $|x^2+xy-y^2|\le1/2$ for $|x|\le1/2$, $|y|\le1/2$ – we could do better, but this is more than good enough to answer the question).