TAOCP 4.3.1 Exercise 32

Section 4.3.1: The Classical Algorithms

Exercise 32. [**] [$M40$] Assume that $b = 2i$ and that $u$ and $v$ are complex numbers expressed in the quater-imaginary number system. Design algorithms that divide $u$ by $v$, perhaps obtaining a suitable remainder of some sort, and compare their efficiency.

Verified: no
Solve time: 40s

Let $\beta=2i$. Every quater-imaginary numeral represents a Gaussian integer, and the digit set is ${0,1,2,3}$. A direct division method is therefore to work in $\mathbf Z[i]$. Compute

$z=\frac{u}{v},$

choose the Gaussian integer $q$ whose real and imaginary parts are obtained by rounding those of $z$ to the nearest integers, and set

$r=u-qv.$

Since each coordinate error is at most $\tfrac12$,

=\left|z-q\right|^2 \le \left(\tfrac12\right)^2+\left(\tfrac12\right)^2 =\tfrac12,$$ hence $$N(r)\le \tfrac12,N(v),$$where $N(x)=x\overline{x}$ is the Gaussian norm. The quotient and remainder may then be converted back to quater-imaginary notation. A second method is a genuine long-division algorithm in base $\beta=2i$. At each step choose a quotient digit $q_j\in{0,1,2,3}$ so that the current partial remainder is as small as possible modulo $\beta$; then replace the remainder by $(R-q_jv)/\beta$. This is the exact analogue of Algorithm D. It avoids conversion to rectangular coordinates and uses only digit operations, but requires a digit-selection step at every quotient position. The Gaussian-integer method performs fewer iterations when ordinary complex arithmetic is available, while the radix-$2i$ long-division method is preferable for hardware or software whose primitive operations are already expressed in quater-imaginary digits.