Statistical Analysis of Certain Binary Division Algorithms

Nondeterministic extensions of the nonrestoring method of binary division have been described by MacSorley [1]. One extension requires that the magnitudes of the divisor and partial remainders be "normal," i. e., in the range [0.5, 1.0). This leads to a time improvement of more than two relative to conventional nonrestoring methods. Other extensions involve the use of several divisor multiples (or trial quotients). A Markov chain model is used here to analyze these methods. Steady-state distributions are determined for the division remainder and performance figures based on both this steady-state distribution and a random distribution are calculated. These are compared with the results of a computer simulation of 214 randmly-chosen division problems using two specific methods of division.