Lowest Terms

  When implementing some of the later operations on dyadic digits, we sometimes generate a numeral $\frac{a}{2^b}$, but cannot guarantee that (a,b) is a valid dyadic digit in its lowest term representation. Given a pair of integers (a,b) with the properties $\vert a\vert \leq 2^b$ and $b \geq 0$, we show how to generate the dyadic digit (a',b') such that $\llbracket (a',b') \rrbracket = \frac{a}{2^b}$.The operation is performed by examining a. If a is zero or odd, the dyadic digit may be obtained directly as follows:

If a is even and not equal to zero, we observe that (b>0) because $(\vert a\vert \leq 2^b)$, and so:

In this case we simply recursively call the function with the arguments (a/2,b-1) in this case until a is zero or odd, at which point we can return the dyadic digit.