Precision requirements for quotient digit selection in high-radix division
Behrooz Parhami · 2001
Digit-recurrence binary dividers are sped up via two complementary methods: keeping the partial remainder in carry-save form and selecting quotient digits in a radix higher than 2, usually in redundant form. The redundancy provides some tolerance to imprecision, so that the quotient digits can be selected based on examining truncated versions of the partial remainder and divisor. No closed form formula for the required precision in the partial remainder and divisor, as a function of the quotient digit set and the partial remainder range, is known. We establish upper bounds on the required precision for the partial remainder and divisor. The bounds are tight in the sense that each is only one bit over a well-known lower bound.