Digit selection for SRT division and square root

摘要

The quotient digit selection in the SRT division algorithm is based on a few most significant bits of the remainder and divisor, where the remainder is usually represented in a redundant representation. The number of leading bits needed depends on the quotient radix and digit set, and is usually found by an extensive search, to assure that the next quotient digit can be chosen as valid for all points (remainder, divisor) in a set defined by the truncated remainder and divisor, i.e., an "uncertainty rectangle." This work presents expressions for the number of bits needed from the truncated remainder and divisor (the truncation parameters), thus eliminating the need for a search through the truncation parameter space for validation. The analysis is then extended to the digit selection in SRT square root algorithms, where it is shown that, in general, it may be necessary to increase the number of leading bits needed for digit determination in a combined divide and square root algorithm. An easy condition to check the number of bits needed is established, also checking the number of initial digits of the root may have to be found by other means, e.g., by table look-up. The minimally redundant, radix-4 combined divide and square root algorithm is finally analyzed and it is shown that, in this case, it can be implemented without such a special table to determine initial digits for the square root.