Methods for constructing lookup tables for division and square-root implementations

Patent metadata

Field	Value
Publication number	US-10423389-B2
Application number	US-201615122771-A
Country	US
Kind code	B2
Filing date	May 13, 2016
Priority date	May 13, 2016
Publication date	Sep 24, 2019
Grant date	Sep 24, 2019

Abstract

Control circuitry coupled to a multiply unit which includes a plurality of stage, each of which may be configured to perform a corresponding arithmetic function, may be configured to retrieve a given entry from a lookup table dependent upon a first portion of a binary representation of an input operand. An error value of an error function evaluated dependent upon a lookup value in a given entry of the plurality of entries is included in a predetermined error range. The control circuitry may be further configured to determine an initial approximation of a result of an iterative arithmetic operation using the first entry and initiate the iterative arithmetic operation using the initial approximation and the input operand.

First claim

What is claimed is:

1. An apparatus, comprising:
a plurality of circuit stages, wherein each circuit stage of the plurality of circuit stages is configured to perform a corresponding arithmetic operation;
a first lookup table including a first plurality of entries that includes a particular value indicative of a first portion of an initial estimate of a result of an iterative arithmetic operation;
a second lookup table including a second plurality of entries that includes a different value indicative of a second portion of the initial estimate of the result of the iterative arithmetic operation; and
a circuit coupled to the plurality of circuit stages, wherein the circuit is configured to:
receive an input operand expressed in a binary representation that includes a fractional part having non-overlapping first, second, and third portions;
retrieve a first value from the first lookup table using the first and second portions of the input operand;
retrieve a second value from the second lookup table using the second portion of the input operand, but not the first or third portions;
multiply the second value and the third portion of the input operand to generate a first intermediate value;
add the first value and the first intermediate value to generate a second intermediate value;
truncate the second intermediate value to generate an initial approximation; and
initiate the iterative arithmetic operation using the initial approximation of the result.

2. The apparatus of claim 1 , wherein the iterative arithmetic operation includes division.

3. The apparatus of claim 1 , wherein the iterative arithmetic operation includes square root.

4. The apparatus of claim 1 , wherein the particular value is based on a value of a particular operation specified in the iterative arithmetic operation evaluated on a particular half open interval.

5. The apparatus of claim 4 , wherein the different value is based on another value of the particular operation evaluated on a different half open interval.

6. A method, comprising:
receiving, by a processor circuit, an input operand for an iterative arithmetic operation, wherein the input operand is expressed in a binary representation that includes a fractional part having non-overlapping first, second, and third portions;
retrieving, by a control circuit included in the processor circuit, a first value from a first lookup table using the first and second portions, wherein the first value is indicative of a first portion of an initial estimate of the iterative arithmetic operation; and
retrieving, by the control circuit, a second value from a second lookup table using the second portion, but not the first and third portions, wherein the second value is indicative of second portion of the initial estimate of the iterative arithmetic operation;
multiplying, by a multiplier circuit included in the processor circuit, the second value and the third portion of the input operand to generated a first intermediate value;
adding, by an adder and truncation circuit included in the processor circuit, the first value and the first intermediate value to generate a second intermediate value;
truncating, by the adder and truncation circuit, the second intermediate value to generate an initial approximation of the iterative arithmetic operation; and
performing, by the processor circuit, the iterative arithmetic operation using the initial approximation and the input operand.

7. The method of claim 6 , further comprising determining the first value and the second value includes determining a plurality of segments over a predetermined interval.

8. The method of claim 7 , further evaluating an error function dependent upon at least one lookup value associated with a given segment of the plurality of segments.

9. The method of claim 8 , modifying at least one segment of the plurality of segments in response to determining a value of the error function is outside a predetermined error range.

10. An apparatus, comprising:
a memory circuit;
a processor circuit coupled to the memory circuit and configured to perform an iterative arithmetic operation based on an input operand and an initial approximation of a result of the iterative arithmetic operation, wherein the input operand is expressed in a binary representation that includes a fractional part having non-overlapping first, second, and third portions, and wherein the processor circuit includes:
a first lookup table including a first plurality of values that includes a particular value indicative of a first portion of an initial estimate of the result of the iterative arithmetic operation;
a second lookup table including a second plurality of values that includes a different value indicative of a second portion of the initial estimate of the result of the iterative arithmetic operation;
a control circuit configured to:
retrieve a first value from the first lookup table using the first and second portions of the input operand;
retrieve a second value from the second lookup table using the second portion, but not the first and third portions;
a multiplier circuit configured to generate a product of the second value and the third portion of the input operand; and
an adder and truncation circuit configured to:
generate a sum of the first value and the product; and
truncate the sum to generate the initial approximation.

11. The apparatus of claim 10 , wherein the iterative arithmetic operation includes division.

12. The apparatus of claim 10 , wherein the iterative arithmetic operation includes square root.

13. The apparatus of claim 10 , wherein the fractional part of the input operand includes a concatenation of the first, second, and third portions.

Assignees

• Oracle Int Corp

Inventors

• Ebergen Josephus
• Nadezhin Dmitry
• Olson Christopher

Classifications

• G06F2101/12

  Reciprocal functions · CPC title

• G06F2101/08

  Powers or roots · CPC title

• G06F1/035

  Reduction of table size {(G06F1/0314 takes precedence)} · CPC title

• G06F1/0356

  by using two or more smaller tables, e.g. addressed by parts of the argument · CPC title

• G06F7/535 Primary

  Dividing only · CPC title