Square-root algorithms for high-speed digital circuits

Two binary algorithms for the square rooting of a sum of two numbers are presented. They are designed for high-speed digital circuits and are based on the classical nonrestoring method. The main difference lies in the replacement of subtractions and additions by the parallel reduction of three summands to two, their sum being unchanged,to eliminate a carry propagation. The term “parallel reduction” is introduced here for the carry-save addition of three summands, positive and negative as well. The two result summands form a successive partial remainder. Their most significant three-bit groups are used to determine the “digits” −1,0,+1 of the square root in a redundant notation. These digits are transformed into the conventional-notation bits, which are used in the further steps of the square-rooting process.