Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

7.4 SQUARE ROOTING

Square rooting deserves special attention because of its frequent use in a number of applications ([ERC1994], [OBE1999]). Although square rooting can be viewed as a particular case of the exponential operation, the similarity with division is a more important consideration for the choice of algorithms. Several techniques in base-B and in binary systems are reviewed in this section.

7.4.1 Digit Recurrence Algorithm—Base-B Integers

Let

be the 2n-digit base-B radicand.

The square root Q and the remainder R are denoted

and

respectively.

The remainder

TABLE 7.8 cos 30°, sind 30°

complies with the condition

ensuring that

The classical pencil and paper method, described in what follows, assumes that all roots of 2-digit numbers are available ((B² − 1) × (B − 1) look-up table). ...