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 ( £ 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 (row of "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 input ( '0' or '1' ) or unused output. 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" cells 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 R is negative (sign bit = '1' ), then Q is too large and can be easily diminished since it is odd.
The main interest of the two extractor versions in to show that digit values '0', '1' or '-1' (i.e. the "BS" notation) can be used for the radix Q.