Efficient hardware divide operation

• US 7,599,982 B1
• Filed: 09/08/2005
• Issued: 10/06/2009
• Est. Priority Date: 09/08/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Rarick, Leonard D.
• Primary Examiner(s): Mai; Tan V
• Application Number:
  US11/223,837
• Time in Patent Office: 1,489 Days
• Field of Search: 708/654
• US Class Current: 708/654
• CPC Class Codes: G06F 2207/5355 Using iterative approximation not using digit recurrence, e.g. Newton Raphson or Goldschmidt
• CPC Class Codes: G06F 2207/5356 Via reciprocal, i.e. calculate reciprocal only, or calculate reciprocal first and then the quotient from the reciprocal and the numerator
• CPC Class Codes: G06F 7/483 Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence
• CPC Class Codes: G06F 7/4873 Dividing
• CPC Class Codes: G06F 7/535 Dividing only
• CPC Class Codes: G06F 7/5525 Roots or inverse roots of single operands

Abstract

One embodiment of the present invention provides a system that uses the Newton-Raphson technique to perform a division operation. During operation, the system receives a numerator a and a denominator b. The system then divides a by b by first using the Newton-Raphson technique to calculate 1/b, and then multiplying 1/b by a to produce the result a/b. While using Newton-Raphson technique to find 1/b, the system first obtains an initial estimate x₀ for 1/b and then iteratively solves the equation x_i+1=x_i(2−bx_i). Each iteration involves: (1) using a multiplier circuit to multiply b by x_i to compute bx_i; (2) performing a bit-wise complement operation on bx_i to compute 2−bx_i, whereby an additional pass through an adder circuit or a multiply/add circuit is not required to perform the subtraction operation. (3) The system then uses the multiplier circuit to multiply x_i by 2−bx_i to compute x_i(2−bx_i).

Claims

1. A method for using the Newton-Raphson technique to perform a division operation within an arithmetic-logic unit (ALU) of a computer system, comprising:

receiving a numerator a and a denominator b; and

dividing a by b within the ALU by first using the Newton-Raphson technique to find 1/b, and then multiplying 1/b by a to produce the result a/b;

wherein using the Newton-Raphson technique to find 1/b involves obtaining an initial estimate x₀ for 1/b and iteratively solving the equation x_i+1=x_i(2−

bx_i) by,

using a multiplier circuit to multiply b by x_i to compute bx_i,

performing a bit-wise complement operation on bx_i to compute 2−

bx_i, whereby an additional pass through an adder circuit or a multiply/add circuit is not required to perform the subtraction operation, and

using the multiplier circuit to multiply x_i by 2−

bx_i to compute x₁(2−

bx_i),

wherein a separate inverter and a separate multiplexer are attached to each bit position of the multiplier circuit to selectively perform a bit-wise complement or a shift operation during specific passes through the multiplier circuit.

2. The method of claim 1, wherein iteratively solving the equation x_i+1=x_i(2−

bx_i) additionally involves performing a left-shift operation at the end of each iteration to renormalize x_i(2−

bx_i).

3. The method of claim 1, wherein obtaining the initial estimate x₀ for 1/b involves using a lookup table or an equivalent method or device to obtain the initial estimate.

4. The method of claim 1, wherein using the multiplier circuit involves using the multiplier circuit to perform a fixed-point multiplication operation.

5. The method of claim 1, wherein using the multiplier circuit to perform a fixed-point multiplication operation involves using a portion of a pipelined floating-point multiplier circuit within the ALU to perform the fixed-point multiplication operation.

6. The method of claim 1, wherein the multiplier circuit performs a Booth encoding on input operands prior to performing the multiplication operation.

7. An apparatus that uses the Newton-Raphson technique to perform a division operation, comprising:

a receiving mechanism configured to receive a numerator a and a denominator b; and

a division mechanism configured to divide a by b by first using the Newton-Raphson technique to find 1/b, and then multiplying 1/b by a to produce the result a/b;

wherein while using the Newton-Raphson technique to find 1/b, the division mechanism is configured to obtain an initial estimate x₀ for 1/b and to iteratively solve the equation x_i+1=x_i(2−

bx_i);

wherein while iteratively solving the equation x_i+1=x_i(2−

bx_i), the division mechanism is configured to,

use a multiplier circuit to multiply b by x_i to compute bx_i,

perform a bit-wise complement operation on bx_i to compute 2−

bx_i, whereby an additional pass through an adder circuit or a multiply/add circuit is not required to perform the subtraction operation, and to

use the multiplier circuit to multiply x_i by 2−

bx_i to compute x_i(2−

bx_i),

wherein a separate inverter and a separate multiplexer are attached to each bit position of the multiplier circuit to selectively perform a bit-wise complement or a shift operation during specific passes through the multiplier circuit.

8. The apparatus of claim 7, wherein while iteratively solving the equation x_i+1=x_i(2−

bx_i), the division mechanism is configured to perform a left-shift operation at the end of each iteration to renormalize x_i(2−

bx_i).

9. The apparatus of claim 7, wherein while obtaining the initial estimate x₀ for 1/b, the division mechanism is configured to use a lookup or an equivalent method or device table to obtain the initial estimate.

10. The apparatus of claim 7, wherein the multiplier circuit is configured to perform a fixed-point multiplication operation.

11. The apparatus of claim 7, wherein the multiplier circuit is a portion of a pipelined floating-point multiplier circuit within the ALU which is configured to perform a fixed-point multiplication operation.

12. The apparatus of claim 7, wherein the multiplier circuit is configured to perform a Booth encoding on input operands prior to performing the multiplication operation.