Browse Prior Art Database

Leading Constant Eliminator for Extended Precision in Pipelined Square Root

IP.com Disclosure Number: IPCOM000113600D
Original Publication Date: 1994-Sep-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 74K

Publishing Venue

IBM

Related People

Faget, RR: AUTHOR

Abstract

A method of Square Root for hardware is disclosed. By transformation of a pipelineable Square Root Multiply-Add algorithm extra precision is gained by elimination of a leading constant from terms used to refine the Root.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Leading Constant Eliminator for Extended Precision in Pipelined Square
Root

      A method of Square Root for hardware is disclosed.  By
transformation of a pipelineable Square Root Multiply-Add algorithm
extra precision is gained by elimination of a leading constant from
terms used to refine the Root.

      One version of the Newton-Raphson algorithm for square root
produces iterative terms which may be pipelineable ideally in a
2-stage Multiply pipeline.  These terms are not used for at least the
second subsequent calculation.

      The unaltered Newton-Raphson algorithm produces terms which are
not pipelineable because each multiply, or multiply-add step produces
a term which is used in the next iterative step.

      For the pipelineable version of the Newton-Raphson algorithm,
the loss of precision that is produced near the least significant bit
of each iterative result term is solved by this invention.  This loss
of precision is a consequence of having to round or truncate the full
precision result to the precision of the source operands of each
iterative expression.  Precision must be maintained beyond the least
significant bit of the result in order to provide correct rounding
for the final result.  With the IEEE floating point standard, a
result must be rounded as if an infinite amount of precision bits
were maintained.  The only way of containing this requirement is by
having precision at least a few bits to the right of the least
significant bit.  Either a different algorithm which reintroduces the
Square root source operand with each iteration, or wider multiply
hardware (wider source than operand size) is necessary to preserve
precision without this invention.

      First, described is the version of the Newton-Raphson algorithm
which is ideally pipelineable in a 2-stage multiply pipe:
  1) Look up seed value, R0, for the approximate reciprocal of the
     square root of the radicand N0.
  2) Perform the pipelineable iterations:
     a) D0 = 0.5 * N0
     b) C0 = R0 * D0
     c) N[i+1]  = R[i]  * N[i]
     d) D[i+1]  = R[i]  * C[i]
     e) R[i+1]  = 1.5 - R[i]  * C[i]
     f) C[i+1]  = R...