US 7,689,642 B1 · Efficient accuracy check for Newton-Raphson divide and square-root operations

Abstract

One embodiment of the present invention provides a system that efficiently performs an accuracy-check computation for Newton-Raphson divide and square-root operations. During operation, the system performs Newton-Raphson iterations followed by a multiply for the divide or square-root operation. This result is then rounded to produce a proposed result. Next, the system performs an accuracy-check computation to determine whether rounding the result to a desired precision produces the correct result. This accuracy-check computation involves performing a single pass through a multiply-add pipeline to perform a multiply-add operation. During this single pass, a Booth encoding of an operand in a multiply portion of the multiply-add pipeline is modified, if necessary, to cause an additional term for the accuracy-check computation to be added to the result of the multiply-add operation. In this way, the accuracy-check computation can be completed without requiring an additional pass through the multiply-add pipeline and without an additional partial-product row in the multiply-add pipeline.

Claims24

Dependent claims

A computer-implemented method for efficiently performing an accuracy-check computation for Newton-Raphson divide and square-root operations, wherein the method comprises:

in a computer system,
performing Newton-Raphson iterations followed by a multiply for a divide or square-root operation to produce a result;
and
performing the accuracy-check computation to determine whether rounding the result to a desired precision produces the correct result;
wherein the accuracy-check computation involves performing a single pass through a multiply-add pipeline to perform a multiply-add operation, and
wherein during the single pass, a Booth encoding of an operand in a multiply portion of the multiply-add pipeline is modified, if necessary, to cause an additional term for the accuracy-check computation to be added to the result of the multiply-add operation;
whereby the accuracy-check computation is completed without requiring an additional pass through the multiply-add pipeline, and without an additional partial-product row in the multiply-add pipeline.

4 more elements

An apparatus which efficiently performs an accuracy-check computation for Newton-Raphson divide and square-root operations, wherein the apparatus comprises:

an arithmetic unit configured to perform Newton-Raphson iterations followed by a multiply for a divide or square-root operation to produce a result;
and
wherein the arithmetic unit is configured to perform the accuracy-check computation to determine whether rounding the result to a desired precision produces the correct result;
wherein during the accuracy-check computation, the arithmetic unit is configured to perform a single pass through a multiply-add pipeline to perform a multiply-add operation;
and
wherein during the single pass, a Booth encoding of an operand in a multiply portion of the multiply-add pipeline is modified, if necessary, to cause an additional term for the accuracy-check computation to be added to the result of the multiply-add operation;
whereby the accuracy-check computation is completed without requiring an additional pass through the multiply-add pipeline, and without an additional partial-product row in the multiply-add pipeline.

4 more elements

A computer system with an arithmetic unit which efficiently performs an accuracy-check computation for Newton-Raphson divide and square-root operations, wherein the computer system comprises:

a processor;
a memory;
an arithmetic unit within the processor configured to perform Newton-Raphson iterations followed by a multiply for a divide or square-root operation to produce a result;
and
wherein the arithmetic unit is configured to perform the accuracy-check computation to determine whether rounding the result to a desired precision produces the correct result;
wherein during the accuracy-check computation, the arithmetic unit is configured to perform a single pass through a multiply-add pipeline to perform a multiply-add operation;
and
wherein during the single pass, a Booth encoding of an operand in a multiply portion of the multiply-add pipeline is modified, if necessary, to cause an additional term for the accuracy-check computation to be added to the result of the multiply-add operation;
whereby the accuracy-check computation is completed without requiring an additional pass through the multiply-add pipeline, and without an additional partial-product row in the multiply-add pipeline.

6 more elements

Dependencies are inferred from the claim text.

Efficient accuracy check for Newton-Raphson divide and square-root operations

Life of this patent

Efficient accuracy check for Newton-Raphson divide and square-root operations

Life of this patent

Abstract

Claims24