# US 2002/0143839 A1 · Computer method and apparatus for division and square root operations using signed digit

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2002/0143839 A1
- Document ID: US20020143839A1
- Status: Published application
- Kind: A1
- Application number: 10/016,902
- Filed: 2001-12-14
- Published: 2002-10-03
- Earliest claimed: 1999-02-01
- Assignees: Compaq Computer Corporation
- Inventors: Mark D. Matson; Robert J. Dupcak; Jonathan D. Krause; Sridhar Samudrala
- Web page: https://patentgrep.com/patent/US20020143839A1

## CPC

- G06F 7/535: Dividing only
- G06F 7/4824: {using signed-digit representation}
- G06F 7/508: using carry look-ahead circuits
- G06F 7/5525: {Roots or inverse roots of single operands}
- G06F 9/3814: {Implementation provisions of instruction buffers, e.g. prefetch buffer; banks}
- G06F 9/3838: {Dependency mechanisms, e.g. register scoreboarding}
- G06F 9/384: {Register renaming}
- G06F 2207/5352: Non-restoring division not covered by G06F7/5375
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The invention provides computer apparatus for performing a square root or division operation generating a root or quotient. A partial remainder is stored in radix-2 or radix-4 signed digit format. A decoder is provided for computing a root or quotient digit, and a correction term dependent on a number of the most significant digits of the partial remainder. An adder is provided for computing the sum of the signed digit partial remainder and the correction term in binary format, and providing the result in signed digit format. The adder computes a carry out independent of a carry in bit and a sum dependent on a Carry_in bit providing a fast adder independent of carry propagate delays. The scaler performs a multiplication by two of the result output from the adder in signed digit format to provide a signed digit next partial remainder.

## Claims

### Claim 1

1) In a computer system, apparatus for performing a square root operation on a radicand, producing a root digit, the apparatus comprising:
a decoder, the decoder computing the root digit and a binary correction term dependent on a number of digits of a current signed digit partial remainder;
an adder connected to the decoder, the adder generating a signed digit result by subtracting the binary correction term from the current signed digit partial remainder; and
a scaler connected to the adder, the scaler computing a next signed digit partial remainder dependent on the signed digit result.

### Claim 2 (depends on 1)

2) An apparatus as claimed in claim 1 wherein the digits of the signed digit partial remainder are selected from the set of minus one, zero and one.

### Claim 3 (depends on 2)

3) An apparatus as claimed in claim 2 wherein the adder computes a carry out independent of a carry in.

### Claim 4 (depends on 3)

4) An apparatus as claimed in claim 3 wherein the number of digits of the current signed digit partial remainder is equal to four.

### Claim 5 (depends on 4)

5) An apparatus as claimed in claim 4 wherein output signals in the adder are initialized to predetermined voltage levels.

### Claim 6 (depends on 1)

6) An apparatus as claimed in claim 1 wherein the scaler computes the next signed digit partial remainder by scaling the current signed digit partial remainder upward.

### Claim 7 (depends on 5)

7) An apparatus as claimed in claim 5 wherein the adder further comprises:
a compute carry out logic accepting as input a digit of the current signed digit partial remainder and a digit of the binary correction term and producing a carry out digit;
a correction plus PR logic accepting as input a digit of the current signed digit partial remainder and a digit of the binary correction term and producing an intermediate sum; and
an add carry logic accepting as input the intermediate sum digit and a carry in digit from a previous signed digit adder and producing a next partial remainder signed digit.

### Claim 8 (depends on 7)

8) An apparatus as claimed in claim 7 wherein
the digit of the current signed digit partial remainder comprises three separate signals and one of the signals is asserted to indicate the state of the current signed digit partial remainder;
the digit of the binary correction term comprises two separate signals and the signals are appropriately asserted to indicate the state of the binary correction term digit;
the digit of the carry out comprises two separate signals and the signals are appropriately asserted to indicate the state of the carry out digit;
the intermediate sum comprises a minus signal and a zero signal;
the digit of the carry in comprises two separate signals and the signals are appropriately asserted to indicate the state of the carry in digit; and
the digit output from the add carry logic comprises three separate signals, a sum zero signal, a sum minus signal and a sum plus signal, and one of the signals is asserted to indicate the state of the add carry logic output digit.

### Claim 9 (depends on 8)

9) An apparatus as claimed in claim 8 wherein the compute carry out logic
sets the state of the carry out digit to zero if the state of the current partial remainder digit is minus one or the state of the current partial remainder digit is set to zero and the state of the binary correction term digit is set to zero; and
sets the state of the carry out digit to one if the state of the current partial remainder digit is one or the state of the current partial remainder digit is set to zero and the state of the binary correction term digit is set to one.

### Claim 10 (depends on 9)

10) An apparatus as claimed in claim 9 wherein the correction plus PR logic
asserts the zero signal if both the binary correction term digit and the current partial remainder digit are set to zero or if neither of the binary correction term digit and the current partial remainder digit is set to zero; and
asserts the minus signal if only one of either the binary correction term digit or the current partial remainder digit is set to a zero.

### Claim 11 (depends on 10)

11) An apparatus as claimed in claim 10 wherein the add carry logic
asserts the sum minus signal if the minus signal is asserted and the carry in is set to zero;
asserts the sum zero signal if the carry in is set to a zero and the zero signal is asserted or if the carry in is set to a one and the minus signal is asserted; and
asserts the sum plus signal if the zero signal is asserted and the carry in is asserted.

### Claim 12 (depends on 1)

12) An apparatus as claimed in claim 1 wherein the digits of the current signed digit partial remainder are selected from the set of minus two, minus one, zero, plus one and plus two.

### Claim 13 (depends on 12)

13) An apparatus as claimed in claim 12 wherein the number of digits of the current signed digit partial remainder is equal to two.

### Claim 14 (depends on 13)

14) An apparatus as claimed in claim 13 wherein the adder computes a carry out independent of a carry in.

### Claim 15 (depends on 14)

15) An apparatus as claimed in claim 14 wherein output signals in the adder are initialized to predetermined voltage levels.

### Claim 16 (depends on 1)

16) An apparatus as claimed in claim 1 wherein the digits of the signed digit partial remainder are selected from a set comprising more than two digit values.

### Claim 17 (depends on 16)

17) An apparatus as claimed in claim 16 wherein the adder further comprises:
a compute carry out logic accepting as input a digit of the current signed digit partial remainder and a digit of the binary correction term and producing a carry out digit;
a correction plus PR logic accepting as input a digit of the current signed digit partial remainder and a digit of the binary correction term and producing an intermediate sum; and
an add carry logic accepting as input the intermediate sum digit and a carry in digit from a previous signed digit adder and producing a next partial remainder signed digit.

### Claim 18 (depends on 17)

18) An apparatus as claimed in claim 17 wherein
the digit of the current signed digit partial remainder comprises five separate signals and one of the signals is asserted to indicate the state of the digit of the current signed digit partial reminder;
the digit of the binary correction term comprises a three signal, a two signal, a one signal and a zero signal and one of the signals is asserted to indicate the state of the binary correcting term digit;
the digit of the carry out comprises two separate signals and the signals are appropriately asserted to indicate the state of the carry out digit;
the intermediate sum comprises a minus one signal, a minus two signal, an intermediate zero signal and a plus one signal;
the digit of the carry in comprises two separate signals and the signals are appropriately asserted to indicate the state of the carry in digit; and
the digit output from the add carry logic comprises five separate signals, a sum zero signal, a sum minus one signal, a sum minus two signal, a sum plus one signal, a sum plus two signal and one of the signals is asserted to indicate the state of the digit output from the add carry logic.

### Claim 19 (depends on 18)

19) An apparatus as claimed in claim 18 wherein the compute carry out logic
sets the state of the carry out digit to one if the state of the current signed partial remainder digit is plus two or if the state of the current signed partial remainder digit is plus one and the zero signal of the binary correction term is not asserted or if the state of the current signed partial remainder digit is zero and neither the two signal or the three signal is asserted.

### Claim 20 (depends on 19)

20) An apparatus as claimed in claim 19 wherein the correction plus PR logic
asserts the minus two signal if the current signed partial remainder digit is set to minus two and the binary correction term's zero signal is asserted or if the current signed partial remainder digit is set to minus one and the binary correction term's three signal is asserted or if the current signed partial remainder digit is set to zero and the binary correction term's two signal is asserted or if the current signed partial remainder digit is set to plus one and the one signal is asserted or if the current signed partial remainder digit is set to plus two and the binary correction term's zero signal is asserted;
asserts the minus one signal if the current signed partial remainder digit is set to minus two and the binary correction term's one signal is asserted or if the current signed partial remainder digit is set to minus one and the binary correction term's zero signal is asserted or if the current signed partial remainder digit is set to zero and the three signal is asserted or if the current signed partial remainder digit is set to plus one and the binary correction term's two signal is asserted or if the current signed partial remainder digit is set to plus two and the binary correction term's plus one signal is asserted;
asserts the intermediate zero signal if the current signed partial remainder digit is set to minus two and the binary correction term's two signal is asserted or if the current signed partial remainder digit is set to minus one and the binary correction term's one signal is asserted or if the current signed partial remainder digit is set to zero and the binary correction term's zero signal is asserted or if the current signed partial remainder digit is set to plus one and the binary correction term's three signal is asserted or if the current signed partial remainder digit is set to plus two and the binary correction term's two signal is asserted;
asserts the plus one signal if the current signed partial remainder digit is set to minus two and the binary correction term's three signal is asserted or if the current signed partial remainder digit is set to minus one and the binary correction term's two signal is asserted or if the current signed partial remainder digit is set to zero and the binary correction term's one signal is asserted or if the current signed partial remainder digit is set to plus one and the binary correction term's zero signal is asserted or if the current signed partial remainder digit is set to plus two and the binary correction term's three signal is asserted.

### Claim 21 (depends on 20)

21) An apparatus as claimed in claim 20 wherein the add carry logic
asserts the sum minus two signal if the minus two signal of the intermediate sum is deasserted and the carry in digit is set to zero;
asserts the sum minus one signal if the minus two signal of the intermediate sum is deasserted and the carry in digit is set to one or if the minus one of the intermediate sum is asserted and the carry in digit is set to zero;
asserts the sum zero signal if the minus one signal of the intermediate sum is asserted; and
asserts the sum plus one signal if the intermediate zero signal is deasserted and the carry in digit is set to one or the plus one signal of the intermediate sum is deasserted and the carry in digit is set to zero; and
asserts the sum plus two signal if the plus one signal of the intermediate sum is deasserted and the carry in digit is set to one.

### Claim 22

22) In a computer system including:
a central processing unit;
a memory connected to the processing unit by a processor bus; and
a floating point logic in the central processing unit comprising an apparatus for performing a square root operation on a radicand, producing a root digit, the apparatus comprising:
a decoder, the decoder computing the root digit and a binary correction term dependent on a number of bits of a current signed digit partial remainder;
an adder connected to the decoder, the adder generating a signed digit result by subtracting the binary correction term from the current signed digit partial remainder; and
a scaler connected to the adder, the scaler computing a next signed digit partial remainder dependent on the signed digit result.

### Claim 23

23) In a computer system, apparatus for performing a square root operation on a radicand, producing a root digit, the apparatus comprising:
a square unit logic;
means, within the square root unit for computing the root digit and a binary correction term dependent on a number of digits of a current signed digit partial remainder;
means, within the square root unit for generating a signed digit result by subtracting the binary correction term from the current signed digit partial remainder; and
means, within the square root unit for computing a next signed digit partial remainder dependent on the signed digit result.

### Claim 24 (depends on 23)

24) An apparatus as claimed in claim 23 wherein the signed digit partial remainder digits are selected from the set of minus one, zero and one.

### Claim 25 (depends on 24)

25) An apparatus as claimed in claim 24 wherein the number of digits of the current signed digit partial remainder is equal to four.

### Claim 26 (depends on 25)

26) An apparatus as claimed in claim 25 wherein the means for generating a signed digit result computes a carry out independent of a carry in.

### Claim 27 (depends on 26)

27) An apparatus as claimed in claim 26 further comprising means for initializing output signals to predetermined voltage levels.

### Claim 28 (depends on 23)

28) An apparatus as claimed in claim 23 wherein the means for computing a next signed digit partial remainder computes the next signed digit partial remainder by shifting the current signed digit partial remainder signed digit to the left.

### Claim 29 (depends on 23)

29) An apparatus as claimed in claim 23 wherein the signed digit partial remainder digits are selected from the set of minus two, minus one, zero, one and minus two.

### Claim 30 (depends on 29)

30) An apparatus as claimed in claim 29 wherein the number of digits of the current signed digit partial remainder is equal to two.

### Claim 31 (depends on 30)

31) An apparatus as claimed in claim 30 wherein the means for generating a signed digit result computes a carry out independent of a carry in.

### Claim 32 (depends on 31)

32) An apparatus as claimed in claim 31 further comprising means for initializing output signals to predetermined voltage levels.

### Claim 33 (depends on 32)

33) An apparatus as claimed in claim 32 wherein the means for computing a next signed digit partial remainder computes the next signed digit partial remainder by multiplying the current signed digit partial remainder by four.

### Claim 34 (depends on 33)

34) An apparatus as claimed in claim 33 wherein the digits of the signed digit partial remainder are selected from a set comprising more than two digit values.

### Claim 35

35) In a computer system, a method for performing a square root operation on a radicand, producing a root digit, comprising the steps of:
computing the root digit and a binary correction term dependent on a number of digits of a current signed digit partial remainder;
generating a signed digit result by subtracting the binary correction term from the current signed digit partial remainder; and
computing a next signed digit partial remainder dependent on the signed digit result.

### Claim 36 (depends on 35)

36) A method as claimed in claim 35 wherein the signed digit partial remainder digits are selected from the set of minus one, zero and one.

### Claim 37 (depends on 36)

37) A method as claimed in claim 36 wherein the number of digits of the current signed digit partial remainder is equal to four.

### Claim 38 (depends on 35)

38) A method as claimed in claim 35 wherein the step of generating a signed digit result further comprises the step of computing a carry out independent of a carry in.

### Claim 39 (depends on 38)

39) A method as claimed in claim 38 further comprising the step of initializing output signals to predetermined voltage levels.

### Claim 40 (depends on 35)

40) A method as claimed in claim 35 wherein the step of computing a signed digit partial remainder computes the next signed digit partial remainder by shifting the current signed digit partial remainder signed digit to the left.

### Claim 41 (depends on 35)

41) A method as claimed in claim 35 wherein the signed digit partial remainder digits are selected from the set of minus two, minus one, zero, one and minus two.

### Claim 42 (depends on 41)

42) A method as claimed in claim 41 wherein the number of digits of the current signed digit partial remainder is equal to two.

### Claim 43 (depends on 42)

43) A method as claimed in claim 42 wherein the step of generating a signed digit result further comprises the step of computing a carry out independent of a carry in.

### Claim 44 (depends on 43)

44) A method as claimed in claim 43 further comprising the step of initializing output signals to predetermined voltage levels.

### Claim 45 (depends on 44)

45) A method as claimed in claim 44 wherein the step of computing a next signed digit partial remainder computes the next signed digit partial remainder by multiplying the current signed digit partial remainder by four.

### Claim 46 (depends on 35)

46) A method as claimed in claim 35 wherein the signed digit partial remainder digits are selected from a set comprising more than two digit values.
