Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Reduced Instruction Implementation of the Newton Iterative Method of the Floating Point Reciprocal and Floating Point Reciprocal Square Root Operation

IP.com Disclosure Number: IPCOM000106045D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 70K

Publishing Venue

IBM

Related People

Arasi, MS: AUTHOR [+4]

Abstract

The typical implementation of the Newton iterative method of division relies upon the derived equation for the zero function result of the function f(x) = (1/x) - b. The equation is zero when b is equal (1/x). Solving of the equation requires an initial guess, which through an iterative method, results in the correct final result of the reciprocal of the number. To reduce the initial guess logic and due to limitations in the complexity of instructions, the equation is generally implemented with multiple iterations of dependant instructions. With slight modification of common instructions, a 30% increase in speed is achieved. A similar benefit is achieved in the reciprocal square root operation.

This text was extracted from an ASCII text file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Reduced Instruction Implementation of the

Newton

Iterative Method of the Floating Point Reciprocal and Floating

Point Reciprocal Square

Root Operation

      The typical implementation of the Newton iterative method of
division relies upon the derived equation for the zero function
result of the function f(x) = (1/x) - b.  The equation is zero when b
is equal (1/x).  Solving of the equation requires an initial guess,
which through an iterative method, results in the correct final
result of the reciprocal of the number.  To reduce the initial guess
logic and due to limitations in the complexity of instructions, the
equation is generally implemented with multiple iterations of
dependant instructions.  With slight modification of common
instructions, a 30% increase in speed is achieved.  A similar benefit
is achieved in the reciprocal square root operation.

     The derivation of Newton's iterative technique for the
reciprocal operation yields the following equation:

       guess = seed * (2 - seed * input_term)
where the resultant guess is at most twice as accurate as the given
seed for the desired result of (1/input_term).  This equation is
derived by finding the zero value of the equation of the line tangent
to the initial guess point, as fully described in numerous other
texts.

     Typical floating point processors contain multiply and add
instructions and the direct combinations (multiply-add), but few
other variations.  Consequently, the implementation of the algorithm
generally involves three load instructions (seed, 2.0 and
input_term), two multiplies and one add (or one multiply-add and one
multiply).  Rearranging the equation into the form:

      guess = -2.0 * (seed * ((seed * input_term)/2.0) - seed)
yields a form that is easily implemented with two modified
instructions mh(mu...