Fast square-root extractor

Fast square-root extractor

We want to get rid of the carry propagation thanks to the use of the "BS" notation, the same "head" and "tail" cells and an architecture similar to the fast division. We bump into three difficulties when trying to use the fast divider for extraction of square roots.

Square root converter

The first difficulty is the root feedback. Like the division circuit, the extractor supplies a partial root Qj in "BS" notation ( '0', '1' and '-1' ). On the other hand, the "head" and "tail" cell of the divider only accepts a partial root in conventional binary representation ( '0' and '1' ). A subtractor could be used to convert each Qj from "BS" to conventional, but that would be at the same time slow and expensive. The converter below use a 4-input, 2-output "trc" cell, derived from the "BK" cell and takes advantage of the delayed inputs.

This circuit has another interest : it gives the input Q converted from "BS" to binary. Besides it gives another output Qm = Q0  1. If the final remainder of the carry-propagation-free extraction is negative, that means that Q is too large (by 1) and Qm is the actual root value, otherwise Q0 is the root value.

Square root conversion cell

Check whether you are acquainted with the logic of the "trc" cell, which convert "on the fly" from "BS" notation into standard binary notation.
Input "si" is a bit from Qj+1, output "so" is the bit of Qj at the same position, input "ci" indicates whether the carry propagates in the cell's position. The carry propagation indicator is used in case of subtraction, it corresponds to the value 'P' of the "BK" cell.

  • if qj = '-1' then { so = si Å ci ; co = 0}//subtraction (sum - carry), carry killed
  • if qj = '0' then { so = si ; co = ci } //sum unchanged, carry propagated
  • if qj = '1' then { so = si ; co = 0 } //sum unchanged, carry killed

Carry-propagation free square root extractor

The fast square-root extractor makes use of the same cell as the fast divider to execute at each step one of the following arithmetic operations:

  • if qj = '-1' then R2j = R2j+2 + 2j * Qj+1 22j-1 // addition
  • if qj = '0' then R2j = R2j+2 // identity
  • if qj = '1' then R2j = R2j+2 2j * Qj+1 22j-1 //subtraction

The second difficulty with respect to division lies in the subtraction of 22j-1 whenever qj = '-1' or qj = '1' . Those cases are detected by an "or" gate the output of which is connected to a negative input of the least significant "tail" cell of each row.
Turned into integers, one row computes S = 4 * R + A qj * ( 4 * Qj+1 + qj )
i.e. S = (R & a1 & a0) qj * ( Qj+1 & '0' & qj ), "&" being the digit-string concatenation.

  Each "head" cell selects the value of one digit qj thanks to the sign of an estimate 2j of the current remainder R2j.

The third and last difficulty is lying in the range. Indeed each Qj must start with a "1" in the most significant position (implicit). This condition is fulfilled if the two most significant bits of the radicand A are not both zero. In other word, A must be "normalized". This "1" is subtracted once from A in the first row thanks to a negative "head" input.
  The root value Q is output at the left in "BS" notation and at the bottom as well in standard binary representation.

Divider and square root extractor

The same circuit can execute either the division or the square root extraction thanks to multiplexers "2 Þ1" inserted into the inputs of some "tail" cells. The first arrows "view" switch around the connections of the inputs of about half of the "tail" cells therefore selecting division or extraction. The second arrow changes the view. For clarity the converter is not drawn for division, but it is always connected to Q and supplies either the quotient or the root in standard binary notation.