Device and method for approximating the square root of a number

• US 5,268,857 A
• Filed: 01/08/1992
• Issued: 12/07/1993
• Est. Priority Date: 01/08/1992
• Status: Expired due to Term

• Current Assignee: Taiwan Semiconductor Manufacturing Company Limited
• Original Assignee: NCR Corporation
• Inventors: Waldron, Robert D., Chen, Dao-Long
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US07/818,302
• Time in Patent Office: 699 Days
• Field of Search: 364/752
• US Class Current: 708/605
• CPC Class Codes: G06F 7/5525 Roots or inverse roots of single operands

Abstract

A device and method for approximating the square root of a binary number N. The device includes hardware for storing N, and a result register for storing x_n, where x_n is a successive approximation of r. The device also includes hardware for iteratively replacing x_n with x_n+1, starting with n=0, where x_n+1 =(Ax_n +N-x_n²)/A, and x₀ is within a predetermined range. "A" is a multiple of 2 so that an operation involving a product or quotient with "A" is effected by a shift operation.

Claims

1. A device for approximating the square root r of a binary number N comprising:

a result register for storing x_n, where x_n is a successive approximation of r;

a first shift register connected to an output of said result register for shifting x_n a predetermined number of places in the direction of its most significant bit, to form a number Ax_n ;

a first adder connected to an output of said shift register for adding Ax_n to N, to form a number Ax_n +N;

a multiplier connected to the output of said result register, for multiplying x_n by itself, to form a number x_n² ;

a second adder connected to outputs of said multiplier and first adder for subtracting x_n² from Ax_n +N, to form a number Ax_n +N-x_n² ; and

a second shift register connected between an output of said second adder and input of said result register for shifting Ax_n +N-x_n² a predetermined number of places in the direction of its least significant bit.

2. The device of claim 1 wherein N is between 0.5 and 2.

3. The device of claim 2 wherein said predetermined number of places for said first and second shift registers is 2 when N is between 1 and 2.

4. The device of claim 2 wherein said predetermined number of places for said first and second shift registers is 1 when N is between 0.5 and 1.

5. A device for approximating the square root r of a binary number B, expressed in scientific notation, comprising:

an exponent register for storing the exponent of B;

a mantissa register for storing the mantissa of B;

a first shift register connected to an output of said mantissa register;

a first multiplexer connected to an output of said shift register and the output of said mantissa register for selectively providing a number N at an output thereof;

a result register for storing x_n, where x_n is a successive approximation of r;

a second shift register connected to an output of said result register for shifting x_n a predetermined number of places in the direction of its most significant bit, to form a number Ax_n ;

a first adder connected to respective outputs of said second shift register and multiplexer for adding Ax_n to N, to form a number Ax_n +N;

a multiplier connected to the output of said result register, for multiplying x_n by itself, to form a number x_n² ;

a second adder connected to outputs of said multiplier and first adder for subtracting x_n² from Ax_n +N, to form a number Ax_n +N-x_n² ; and

a third shift register connected between an output of said second adder and input of said result register for shifting Ax_n +N-x_n² a predetermined number of places in the direction of its least significant bit.

6. The device of claim 5 further comprising:

a third adder connected to an output of said exponent register for adding "1" to said exponent;

a second multiplexer connected to the output of said exponent register and an output of said third adder for selectively providing a number E at an output thereof; and

a fourth shift register connected to an output of said second multiplexer for shifting E one place in the direction of its least significant bit.

7. The device of claim 6 wherein said first shift register shifts the mantissa of B one place.

8. The device of claim 7 wherein said first shift register shifts the mantissa of B in the direction of its least significant bit.

9. The device of claim 8 further comprising:

a control line connected between said exponent register and said first and second mutliplexers to provide the least significant bit of the exponent of N as a control signal thereto.

10. The device of claim 9 further comprising:

an exponent result register for receiving the output of said fourth shift register.