Square root digit recurrence

Patent metadata

Field	Value
Publication number	US-10809980-B2
Application number	US-201715622429-A
Country	US
Kind code	B2
Filing date	Jun 14, 2017
Priority date	Jun 14, 2017
Publication date	Oct 20, 2020
Grant date	Oct 20, 2020

Abstract

A data processing apparatus is provided, for performing a digit-recurrence square root operation on an input value. Receiver circuitry receives a remainder value of a previous iteration of the digit-recurrence square root operation. Comparison circuitry compares most significant bits of the remainder value of the previous iteration with a number of selection constants, in order to output a next digit of a result of the digit-recurrence square root operation. The comparison circuitry compares at most 3 fractional bits of the remainder value of the previous iteration with the plurality of selection constants.

First claim

We claim:

1. A data processing apparatus to perform a digit-recurrence square root operation on an input value, comprising:
receiver circuitry to receive a remainder value of a previous iteration of said digit-recurrence square root operation, and a partial result of said digit-recurrence square root operation from a previous iteration; and
comparison circuitry comprising comparators configured to communicate with said receiver circuitry and to compare most significant bits of said remainder value of said previous iteration of said digit-recurrence square root operation with a plurality of selection constants of said digit-recurrence square root operation, to output a next digit of a result of said digit-recurrence square root operation,
said comparison circuitry further comprising selection circuitry to select one of a plurality of subsets of said plurality of selection constants to compare to a predetermined number of fractional bits of said remainder value based on most significant bits of said partial result of said digit-recurrence square root operation from a previous iteration; and
storage circuitry, accessible to said selection circuitry, to store said plurality of selection constants of said digit-recurrence square root operation, wherein:
said most significant bits of said remainder value comprise said predetermined number of fractional bits,
said predetermined number is at most 3, and
said selection constants comprise at most 3 fractional bits
said comparison circuitry comprises deviation circuitry to replace a single selection constant in said one of said plurality of subsets in response to a current iteration of said digit-recurrence square root operation being a predetermined iteration.

2. A data processing apparatus according to claim 1 , comprising:
remainder determination circuitry to determine a remainder value of a current iteration based on said remainder value of said previous iteration, and a partial result of said digit-recurrence square root operation, and to provide said remainder value of said current iteration to said receiving circuitry.

3. A data processing apparatus according to claim 1 , wherein
said subset of said plurality of selection constants has a number of elements dependent on a digit set of said next digit.

4. A data processing apparatus according to claim 3 , wherein
said subset of said plurality of selection constants has one element for each element of said digit set, minus 1.

5. A data processing apparatus according to claim 1 , wherein
said plurality of subsets comprises a number of subsets dependent on a number of said most significant bits of said partial result of said digit-recurrence square root operation from a previous iteration.

6. A data processing apparatus according to claim 1 , wherein
said plurality of subsets comprises a number of subsets equal to 2 n−1 +1, wherein n is equal to the number of most significant fractional bits of said partial result of said digit-recurrence square root operation from a previous iteration.

7. A data processing apparatus according to claim 1 , wherein
said plurality of subsets consists of a number of subsets equal to 2 n−1 +1, wherein n is equal to the number of most significant fractional bits of said partial result of said digit-recurrence square root operation from a previous iteration.

8. A data processing apparatus according to claim 7 , wherein
said comparison circuitry is further configured to select said one of a plurality of subsets independently of a current iteration.

9. A data processing apparatus according to claim 1 , wherein
said deviation circuitry is responsive to at most three situations in which a single selection constant in said one of said plurality of subsets is replaced.

10. A data processing apparatus according to claim 1 , wherein
a radix of said digit-recurrence square root operation is 4.

11. A data processing apparatus according to claim 1 , wherein
said plurality of selection constants are exclusively selected from the values: 12/8, 13/8, 15/8, 16/8, 18/8, 20/8, 22/8, 24/8, 4/8, 6/8, 8/8, −4/8, −6/8, −8/8, −12/8, −11/8, −13/8, −15/8, −16/8, −18/8, −20/8, −22/8, and −24/8 or numerical equivalents thereof.

12. A data processing method for performing a digit-recurrence square root operation on an input value, comprising:
receiving, by receiver circuitry, a remainder value of a previous iteration of said digit-recurrence square root operation, and a partial result of said digit-recurrence square root operation from a previous iteration;
comparing, by comparison circuitry including comparators communicating with said receiver circuitry, most significant bits of said remainder value of said previous iteration of said digit-recurrence square root operation with a plurality of selection constants of said digit-recurrence square root operation, to output a next digit of a result of said digit-recurrence square root operation;
selecting, by selection circuitry included the comparison circuitry, one of a plurality of subsets of said plurality of selection constants to compare to a predetermined number of fractional bits of said remainder value based on most significant bits of said partial result of said digit-recurrence square root operation from a previous iteration; and
storing, by storage circuitry accessible to said selection circuitry, said plurality of selection constants of said digit-recurrence square root operation, wherein:
said most significant bits of said remainder value comprise said predetermined number of fractional bits,
said predetermined number is at most 3,
said selection constants comprise at most 3 fractional bits, and
said step of comparing comprises replacing a single selection constant in said one of said plurality of subsets in response to a current iteration of said digit-recurrence square root operation being a predetermined iteration.

Assignees

• Advanced Risc Mach Ltd

Inventors

• Bruguera Javier Diaz
• Russinoff David M

Classifications

• G06F2207/5526

  Roots or inverse roots of single operands · CPC title

• G06F7/552 Primary

  Powers or roots {, e.g. Pythagorean sums} · CPC title