Implementing a square root operation in a computer system

Patent metadata

Field	Value
Publication number	US-9612800-B2
Application number	US-201414452358-A
Country	US
Kind code	B2
Filing date	Aug 5, 2014
Priority date	Aug 5, 2014
Publication date	Apr 4, 2017
Grant date	Apr 4, 2017

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.

First claim

The invention claimed is:

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

1

b

 denoted as p 0 ; and for iterations in which an iteration index i=0, . . . , c, c being a predetermined number greater than or equal to 0:
(i) performing a first computation using multiplier logic of the computer system to determine a first intermediate parameter r i based on a multiplication of the input value b with p i ;
(ii) performing a second computation using the multiplier logic to determine a second intermediate parameter s i based on a multiplication of the first intermediate parameter r i with p i ;
(iii) when i<c, computing a refined approximation of

1

b

denoted as p i+1 using the multiplier logic based on a multiplication of the second intermediate parameter s i with p i , incrementing i, and repeating steps (i) and (ii); and
(iv) when i=c, computing with the multiplier logic the value of √{square root over (b)} based on a multiplication of first intermediate parameter r c with second intermediate parameter s c .

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

1

b

;

(ii) performing a second computation with the multiplier logic to determine a second intermediate parameter s i , for the current iteration based on a multiplication of the first intermediate parameter r, for the current iteration with the previous approximation of

1

b

;

and
(iii) performing a third computation with the multiplier logic to determine a refined approximation of

1

b

for use in a subsequent iteration based on a multiplication of the second intermediate parameter s i for the current iteration with the previous approximation of

1

b

.

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

1

b

;

the second computation comprises determining the second intermediate parameter s c in accordance with the equation

s
c

=

1
2

⁢

(

1
-

r
c

⁢

p
c

)

;

and
the computation when i=c comprises determining the value of √{square root over (b)}, denoted result, in accordance with the equation result=r i s 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

1

b

;

the second computation comprises determining the second intermediate parameter s i in accordance with the equation

s
i

=

1
2

⁢

(

1
-

r
i

⁢

p
i

)

;

and
the computation when i=c comprises determining the value of √{square root over (b)}, denoted result, in accordance with the equation result=r i s i +r 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.

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

1

b

denoted as p i ;
(ii) perform a second computation to determine a second intermediate parameter s i based on a multiplication of the first intermediate parameter r i with p i
(iii) when i<c, computing a refined approximation of

1

b

denoted as p i+1 based on a multiplication of the second intermediate parameter s i with p i , incrementing i, and repeating steps (i) and (ii), and
(iv) when i=c determining the value of √{square root over (b)} based on a multiplication of first intermediate parameter r c with second intermediate parameter s c .

7. A non-transitory computer readabl

Assignees

• Imagination Tech Ltd
• Imagination Tech Ltd

Inventors

• Rarick Leonard

Classifications

• G06F2207/5355

  Using iterative approximation not using digit recurrence, e.g. Newton Raphson or Goldschmidt · CPC title

• G06F7/5525 Primary

  Roots or inverse roots of single operands · CPC title