An N-Predictor-Corrector Iterative Algorithm for Expanding Number of Bits in Binary Division
Huang Faqian · Journal of Beijing Jiaotong University · 2009
An expanding number of binary division bits algorithm is presented based on divide-and-conquer strategy and N-predictor-corrector iterative method.The algorithm iterates by using high-order binary elements of the divisor to find an estimate of quotient and subtracting the quotient multiplied by the low-order elements from the dividend to find a remaining dividend.The estimate is always more than or equal to the true quotient,so that the adjustment is always nonpositive.Theory analysis and demonstration,and computer simulation lead to the conclusion that the adjustment is in the set {0,-1,-2}.Probability curve of each adjustment within 32-bit division is also presented to show effectiveness of the algorithm.Experiments indicate that the algorithm is about 3～10 times fast than comparison division,depending on bit length of basic division.In addition,this algorithm can produce an exact remainder,which makes implementation of the exact rounding specifications(e.g.,IEEE floating-point) straight forward.