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

image

be the 2n-digit base-B radicand.

The square root Q and the remainder R are denoted

image

and

image

respectively.

The remainder

image

TABLE 7.8 cos 30°, sind 30°

image

complies with the condition

image

ensuring that image

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

Get Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.