IMPLEMENTING A SQUARE ROOT OPERATION IN A COMPUTER SYSTEM

• US 20160041947A1
• Filed: 08/05/2014
• Published: 02/11/2016
• 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
• Granted Patent: US 9,612,800 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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, the method using an iterative converging approximation technique for determining converging approximations of

2. The method of claim 1 wherein said implementing one or more iterations of the iterative converging approximation technique using multiplier logic of the computer system comprises implementing a plurality of iterations of the iterative converging approximation technique, and wherein said previous approximation of

3. The method of claim 2 wherein each of at least one non-concluding iteration of the plurality of iterations of the iterative converging approximation technique 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

4. The method of claim 1 wherein:

the first computation of the concluding iteration 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

5. The method of claim 1 wherein:

the first computation of the concluding iteration 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

6. 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.

20. A computer readable storage medium having encoded thereon:

(i) computer readable code for generating a computer system according to claim 7, or (ii) computer readable code adapted to perform the steps of the method of claim 1 when the code is run on a computer.

7. 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 an iterative converging approximation module arranged to receive an initial approximation of

8. The computer system of claim 7 wherein the iterative converging approximation module further comprises:

a memory for storing at least the first intermediate parameter r_c 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 of the iterative converging approximation technique which are implemented based on:

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

10. The computer system of claim 7 wherein said one or more iterations of the iterative converging approximation technique comprises only one iteration, and wherein said previous approximation of

11. The computer system of claim 7 wherein said one or more iterations of the iterative converging approximation technique comprises a plurality of iterations, and wherein said previous approximation of

12. The computer system of claim 11 wherein to implement each of at least one non-concluding iteration of the plurality of iterations of the iterative converging approximation technique the iterative converging approximation module is configured to:

(i) perform a first computation with the multiplier logic 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

13. The computer system of claim 7 wherein the iterative converging approximation module is configured to perform three computations with the multiplier logic for each of the one or more iterations of the iterative converging approximation technique.

14. The computer system of claim 7 wherein the iterative converging approximation module is configured to implement the concluding iteration without determining a refined approximation of

15. The computer system of claim 7 wherein the iterative converging approximation module is configured such that:

the first computation of the concluding iteration 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

16. The computer system of claim 7 wherein the iterative converging approximation module is configured such that for the concluding iteration:

the first computation performed by the multiplier logic comprises rounding down to determine the first intermediate parameter r_c;

the second computation performed by the multiplier logic comprises rounding down to determine the second intermediate parameter s_c; and

the concluding computation performed by the multiplier logic comprises rounding down to determine the value of √

{square root over (b)}.

17. The computer system of claim 7 further comprising check logic which is configured to:

receive the determined value of √

{square root over (b)} from the iterative converging approximation module; 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.

18. The computer system of claim 7 wherein the iterative converging approximation module is configured such that:

the first computation of the concluding iteration 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

19. The computer system of claim 7 further comprising initial approximation logic configured to:

obtain the initial approximation of