This paper investigates a family of division algorithms (referred to as Sweeney-Robertson-Tocher (SRT)) as examples of dynamical systems. Although the main result of the paper can be understood without recourse to the dynamical systems theory literature, some preliminary familiarity with this important field of mathematics is probably needed to really appreciate the paper.
SRT can be viewed naturally as a discrete dynamical system, in that the partial remainders and quotient bits, pi+1 ,qi+1, can be expressed as polynomial functions (in fact, linear functions) of pi, qi+1. The subtlety is that one of some finite number of functions is applied according to some branching conditions. In the case of SRT, these conditions are expressible as inequalities in pi and |pi|.
The authors convert SRT into a transformation T on reals in the half-closed interval [0,1), and study orbits of T on subsets of [0,1). An orbit of S ⊆ [0,1) is the sequence of subsets Ti S, where i may be negative in case T is invertible.
The main result is that T is essentially a Bernoulli transformation. The original Bernoulli transformation is the shift xi+1 = 2xi mod 1 for x ∈ [0,1). This transformation is a bit shifting operator on the binary expansion of x. That the SRT transformation T is Bernoulli makes possible the computation of quantities that enable one to further compute such things as the expected number of shift register operations used in an SRT division, and obtain estimates on the expected SRT performance.
The authors extend their result to more complex SRT algorithms, although they know that certain restrictions on divisors need to be imposed to preserve the Bernoulli property for T. Since many arithmetic algorithms can be fairly easily expressed as dynamical systems, it should be possible to apply the methods of this paper to characterizations of their global properties.
