Efficient hardware square-root operation

摘要

One embodiment of the present invention provides a system that uses the Newton-Raphson technique to compute a square-root. During operation, the system receives a radicand b. Next, the system calculates the square root of b, √{square root over (b)}, by first using the Newton-Raphson technique to find 1/√{square root over (b)}, and then multiplying 1/√{square root over (b)} by b to produce √{square root over (b)}. While using the Newton-Raphson technique to find 1/√{square root over (b)}, the system first obtains an initial estimate x0 for 1/√{square root over (b)} and then iteratively solves the equation $x_{i+1}=x_i\left(\frac{3-{\mathrm{bx}}_i^2}{2}\right).$ Each iteration involves: (1) using a multiplier circuit twice to compute bxi2; (2) performing a bit-wise complement operation on bxi2, shifting the result, and modifying the first two bits of the result to compute $\frac{3-{\mathrm{bx}}_i^2}{2},$ whereby an additional pass through an adder circuit or a multiply/add circuit is not required to perform the subtraction operation; and finally (3) using the multiplier circuit to multiply xi by $\frac{3-{\mathrm{bx}}_i^2}{2}$ to compute $x_i\left(\frac{3-{\mathrm{bx}}_i^2}{2}\right).$