Square root extractor

Square root extraction

The square-root extraction is relatively infrequent. Nevertheless, it is used among other things for Euclidean distance and least square. The square-root operator is similar to the division's one, therefore most of what we already know about division applies as well to square root. Often the same operator is used either for division or for extraction, collision of the two operations being too rare to justify two operators, moreover each very costly.

Square root extraction algorithm

In the drawing below, the area of each red rectangle represents one bit weight. Only the '1' are drawn. Therefore the total area shown is the weighted sum of all the bits. The goal of the game is to find a square with an area equal to a given argument, represented by the area of a blue circle, just by observing one test bit ( £ or > ) and by clicking the bits representing the side of the square. After convergence the sough after number is the side of the square. Click on objects to disclose their area.

Square root extractor

We want to get Q = ÖA. This is equivalent to Q = A ÷ Q. Therefore if Q is written on n bits, A is written on 2n bits. Let us build a series Qn, Qn-1, ... Q2, Q1, Q0 and a series R2n, R2n-2, ... R4, R2, R0 such that the invariant A = Qj * Qj + R2j holds for all j. The recurrence is : Qj-1 = Qj + qj-1 * 2j-1                              ( this is merely a concatenation ) R2j-2 = R2j – qj-1 * 2j-1 * ( 2 * Qj + 2j-1)  ( this is a conditional subtraction ) with the initial conditions : Qn = 0 R2n = A. When the recurrence stops, we have Q = Q0 = Si qi * 2i. R = R0 is the final remainder of the square root extraction. If the false additions "+" are replaced by concatenations "&", the recurrence becomes: Qj-1 = Qj & qj-1 R2j-2 = R2j – qj-1* 2j * ( Qj & 0 1 )           ( conditional subtraction )

Restoring square root extractor

The restoring square-root extractor utilizes the same conditional subtractor ( "SC" ) cells as the restoring divider. if R2j ³ ( Qj & 0 1 ) then { qj-1 = '1' ; R2j-2 = R2j – ( Qj & 0 1 ) } //subtraction if R2j < ( Qj & 0 1 ) then { qj-1 = '0' ; R2j-2 = R2j} // identity

Many cells of this circuit have constant inputs ( '0' or '1' ). They are not simplified here as they are in the restoring divider.

Non-restoring root extractor

The non-restoring square root extractor uses the same add/subtract "AS" calls as the non-restoring divider. if R2j ³ 0 then { qj-1 = '1' ; R2j-2 = R2j – ( Qj & 0 1 ) } //subtraction if R2j < 0 then { qj-1 = '-1' ; R2j-2 = R2j + ( Qj & 11 ) } // addition

Since the radix Q is positive, its most significant digit qn is always '1'. This extractor always gives an odd radix Q. If the final remainder is negative (sign bit = 1), then Q is too large and can be easily reduced since it is odd. The main interest of the two extractor versions in to show that digit values '0', '1' or '-1' ("BS" notation) can be used for the radix .