Implementing a square root operation in a computer system

• US 9,612,800 B2
• Filed: 08/05/2014
• Issued: 04/04/2017
• Est. Priority Date: 08/05/2014
• Status: Active Grant

• Current Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Original Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Inventors: Rarick, Leonard
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US14/452,358
• Publication Number:
  US 20160041947A1
• Time in Patent Office: 973 Days
• Field of Search: 708605
• CPC Class Codes: G06F 2207/5355 Using iterative approximation not using digit recurrence, e.g. Newton Raphson or Goldschmidt
• CPC Class Codes: G06F 7/5525 Roots or inverse roots of single operands

Abstract

A method and computer system are provided for implementing a square root operation using an iterative converging approximation technique. The method includes fewer computations than conventional methods, and only includes computations which are simple to implement in hardware on a computer system, such as multiplication, addition, subtraction and shifting. Therefore, the methods described herein are adapted specifically for being performed on a computer system, e.g. in hardware, and allow the computer system to perform a square root operation with low latency and with low power consumption.

Claims

1. A method of implementing a square root operation in a computer system to determine a value of √

{square root over (b)}, where b is an input value, comprising;

obtaining an initial approximation of

2. The method of claim 1 wherein computing an initial approximation comprises:

(i) performing a first computation with the multiplier logic of the computer system to determine a first intermediate parameter r_i for the current iteration based on a multiplication of the input value b with a previous approximation of

3. The method of claim 1 wherein:

the first computation comprises determining the first intermediate parameter r_i in accordance with the equation r_i=bp_i

4. The method of claim 1 wherein:

the first computation comprises determining the first intermediate parameter r_c in accordance with the equation r_i=bp_i

5. The method of claim 1 further comprising scaling an initial input value by an even power of two to determine the input value b such that 1≦

b<

4.

7. A non-transitory computer readable storage medium having stored thereon computer executable instructions that when executed cause at least one processor to perform the method as set forth in claim 1.

6. A computer system configured to implement a square root operation to determine a value of √

{square root over (b)}, where b is an input value, the computer system comprising multiplier logic configured to;

for iterations in which an iteration index i=0, . . . , c, c being a predetermined number greater than or equal to 0;

(i) perform a first computation to determine a first intermediate parameter r_i based on a multiplication of the input value b with a previous approximation of

8. The computer system of claim 6 further comprising:

a memory for storing at least the first intermediate parameter r_i and the previous approximation of

9. The computer system of claim 8 wherein the control module is further configured to control the number of iterations which are implemented based on:

(i) the number of bits of accuracy of the initial approximation of

10. The computer system of claim 6 wherein to implement at least iteration multiplier logic is configured to:

(i) perform a first computation to determine a first intermediate parameter r_i for the current iteration based on a multiplication of the input value b with a previous approximation of

11. The computer system of claim 6 wherein the multiplier logic is configured to perform three computations for each of one or more iterations.

12. The computer system of claim 6 wherein the multiplier logic is configured to implement a concluding iteration without determining a refined approximation of

13. The computer system of claim 6 wherein the multiplier logic is configured such that:

the first computation comprises determining the first intermediate parameter r_c in accordance with the equation r_c=bp_c where p_c is the previous approximation of

14. The computer system of claim 6 wherein the multiplier logic is configured such that for a concluding iteration:

the first computation comprises rounding down to determine the first intermediate parameter r_c;

the second computation comprises rounding down to determine the second intermediate parameter s_c; and

the concluding computation comprises rounding down to determine the value of √

{square root over (b)}.

15. The computer system of claim 6 further comprising check logic which is configured to:

receive the determined value of √

{square root over (b)}; and

perform a check procedure on the determined value of √

{square root over (b)} in accordance with a rounding mode to check that the determined value of √

{square root over (b)} is correct in accordance with the rounding mode.

16. The computer system of claim 6 wherein the multiplier logic is configured such that:

the first computation comprises determining the first intermediate parameter r_c in accordance with the equation r_c=bp_c where p_c is the previous approximation of

17. The computer system of claim 6 further comprising initial approximation logic configured to:

obtain the initial approximation of

18. A non-transitory computer readable storage medium having stored thereon computer readable code that when processed by an integrated circuit manufacturing system causes the integrated circuit manufacturing system to generate a computer system according to claim 6.