next up previous contents
Next: High-Level Operations Up: Division Previous: Output negative digits

Extending division to the whole real line

Extending the division algorithm to work on the whole real line is relatively trivial. We now have an algorithm which will compute

\frac{x}{4y} \qquad \textrm{where } x \in [-1,1], \vert y\vert \in \left[\frac{1}{4}, 1\right]\end{displaymath}

with the precondition that y is of the form (1::0::y') or (1::1::y'). We can now implement the full division algorithm using the following observation:

\frac{(x,e)}{(y,f)} = \frac{x \times 2^e}{y \times 2^f} = \frac{x}{4y} \times 2^{2+e-f}\end{displaymath}

Appendix B gives the Haskell implementation of the entire division algorithm. The structure closely follows the approach taken in describing the algorithm here, and gives a succinct recursive definition for the algorithm.

Martin Escardo