Browse Prior Art Database

Synthetic Newton-Raphson Error Term Determination for Division And Square Root

IP.com Disclosure Number: IPCOM000119580D
Original Publication Date: 1991-Feb-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 3 page(s) / 112K

IBM

Related People

Faget, RR: AUTHOR

Abstract

One of the Newton-Raphson convergence algorithms for Division and another one for Square Root contain an error term that is a Subtraction-Multiplication operation. This error term may be approximated as the one's complement of another term in the case of Division and as the one's complement of another term followed by a two bit addition in the case of Square Root. The error introduced only affects the least significant bit of the error term and may, therefore, be utilized for all iterations of the algorithms except for the final ones which require precision at or beyond the least significant bit.

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

Synthetic Newton-Raphson Error Term Determination for Division And
Square Root

One of the Newton-Raphson convergence algorithms for
Division and another one for Square Root contain an error term that
is a Subtraction-Multiplication operation.  This error term may be
approximated as the one's complement of another term in the case of
Division and as the one's complement of another term followed by a
two bit addition in the case of Square Root.  The error introduced
only affects the least significant bit of the error term and may,
therefore, be utilized for all iterations of the algorithms except
for the final ones which require precision at or beyond the least
significant bit.

The fastest techniques for performing division involve the use
of Multiply or Multiply-Add hardware which use a Newton-Raphson
algorithm or algebraic equivalent.  The Newton-Raphson formula, Xi+1
= Xi*(2 - Xi*D), which describes an approximation for the reciprocal
of a Div isor D can be multiplied by the Dividend N to produce an
approximation for the Quotient.  The above formula is used repeatedly
to obtain a desired precision for a reciprocal and every application
of the formula results in a doubling of the precision of the
reciprocal.  Each iteration involves a Multiplication and Subtraction
which must wait until the previous iteration is finished, followed by
another Multiplication which must wait for the result of the previous
subtraction.  A Quotient convergence algorithm, which is
algebraically equivalent to the Newton-Raphson formula, does
iterative calculations for the Quotient rather than the reciprocal.
One extra multiplication is required per iteration, but each
calculation is pipelineable, which means that for a two-stage pipe,
any one calculation does not depend on the previous calculation for a
result as one of the input operands for that calculation.  Two-stage
Multiply-Add pipelines require one fewer machine cycle per iteration
using the Quotient convergence algorithm as opposed to the unaltered
Newton-Raphson formula.  The three terms which make up the Quotient
convergence formula are:
Ni+1 = Ni*Ri
Ri+1 = 2-Di*Ri
Di+1 = Di*Ri

To provide initial values, R0 is given by a lookup table,
commonly implemented with combinatorial logic or ROM, and is the
"seed" value for the reciprocal of the Divisor out to a few bits of
precision.  Thi...