Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

16.8 SQUARE ROOT

A basic square-rooter deduced from Algorithm 16.7 is shown in Figure 16.10. If e₁ is even, the square-rooter input is

and if e₁ is odd

In both cases s′ can be represented as a (2.p + 5)-digit integer. The square-root algorithms (Chapter 7) generate Q and R such that

so that Q² ≤ s′ and (Q + 1)² > s′. Observe that Q is a (p + 3)-digit integer and R a (p + 4)-digit integer; then, according to (16.33),

so that (Q.B^{−(p + 2)})² ≤ s′.B^{−2.(p + 2)} and (Q.B^{−(p + 2)} + B^{−(p + 2)})² > s′.B^{−2.(p + 2)}.

Thus Q.B^{−(p + 2)} is the square root of either s₁ (16.31) or s₁/B (16.32), with a precision of p + 2 fractional digits. The sticky digit is equal to 1 if R > 0 and to 0 if R = 0. The final approximation of the exact result is

Figure 16.10 Square-rooter.