Higher Radix Square Rooting

A general discussion on nonrestoring square root algorithms is presented, showing bounds and constraints delimiting the space of feasible algorithms, for all the choices of radix, digit set and representation of the partial remainder. Two classes of algorithms are then derived from the general discussion, and it is shown how it is possible to determine two parameters with a relevant impact on the implementation: the number of radicand bits to be inspected in order to obtain a starting value, and the number of partial remainder bits to be examined for digit selection. The algorithms for the specific case of radix 4 digit set {-2, -1, 0, +1, +2}, and partial remainder represented in carry-save form are derived in order to show that the algorithms introduced can lead to better results than those obtained with algorithms previously presented