Implementing a square root operation in a computer system

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 $\frac{1}{\sqrt{b}}$ denoted as p.sub.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.sub.i based on a multiplication of the input value b with p.sub.i; (ii) performing a second computation using the multiplier logic to determine a second intermediate parameter s.sub.i based on a multiplication of the first intermediate parameter r.sub.i with p.sub.i; (iii) when i<c, computing a refined approximation of $\frac{1}{\sqrt{b}}$ denoted as p.sub.i+1 using the multiplier logic based on a multiplication of the second intermediate parameter s.sub.i with p.sub.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.sub.c with second intermediate parameter s.sub.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.sub.i for the current iteration based on a multiplication of the input value b with a previous approximation of $\frac{1}{\sqrt{b}};$ (ii) performing a second computation with the multiplier logic to determine a second intermediate parameter s.sub.i, for the current iteration based on a multiplication of the first intermediate parameter r, for the current iteration with the previous approximation of $\frac{1}{\sqrt{b}};$ and (iii) performing a third computation with the multiplier logic to determine a refined approximation of $\frac{1}{\sqrt{b}}$ for use in a subsequent iteration based on a multiplication of the second intermediate parameter s.sub.i for the current iteration with the previous approximation of $\frac{1}{\sqrt{b}}.$

3. The method of claim 1 wherein: the first computation comprises determining the first intermediate parameter r.sub.i in accordance with the equation r.sub.i=bp.sub.i $\frac{1}{\sqrt{b}};$ the second computation comprises determining the second intermediate parameter s.sub.c in accordance with the equation $s_c=\frac{1}{2}\left(1-r_c{p}_c\right);$ and the computation when i=c comprises determining the value of {square root over (b)}, denoted result, in accordance with the equation result=r.sub.is.sub.i.

4. The method of claim 1 wherein: the first computation comprises determining the first intermediate parameter r.sub.c in accordance with the equation r.sub.i=bp.sub.i $\frac{1}{\sqrt{b}};$ the second computation comprises determining the second intermediate parameter s.sub.i in accordance with the equation $s_i=\frac{1}{2}\left(1-r_i{p}_i\right);$ and the computation when i=c comprises determining the value of {square root over (b)}, denoted result, in accordance with the equation result=r.sub.is.sub.i+r.sub.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 1b<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.sub.i based on a multiplication of the input value b with a previous approximation of $\frac{1}{\sqrt{b}}$ denoted as p.sub.i; (ii) perform a second computation to determine a second intermediate parameter s.sub.i based on a multiplication of the first intermediate parameter r.sub.i with p.sub.i (iii) when i<c, computing a refined approximation of $\frac{1}{\sqrt{b}}$ denoted as p.sub.i+1 based on a multiplication of the second intermediate parameter s.sub.i with p.sub.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.sub.c with second intermediate parameter s.sub.c.

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.

8. The computer system of claim 6 further comprising: a memory for storing at least the first intermediate parameter r.sub.i and the previous approximation of $\frac{1}{\sqrt{b}}$ p.sub.i; and a control module configured to control which values are provided to the multiplier logic for the respective computations.

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 $\frac{1}{\sqrt{b}},$ and (ii) a desired number of bits of accuracy of the determined value of {square root over (b)}.

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.sub.i for the current iteration based on a multiplication of the input value b with a previous approximation of $\frac{1}{\sqrt{b}};$ (ii) perform a second computation to determine a second intermediate parameter s.sub.i for the current iteration based on a multiplication of the first intermediate parameter r.sub.i for the current iteration with the previous approximation of $\frac{1}{\sqrt{b}}:$ and (iii) perform a third computation to determine a refined approximation of for use in a subsequent iteration based on a multiplication of the second intermediate parameter s.sub.i for the current iteration with the previous approximation of $\frac{1}{\sqrt{b}}.$

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 $\frac{1}{\sqrt{b}}$ on the concluding iteration.

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.sub.c in accordance with the equation r.sub.c=bp.sub.c where p.sub.c is the previous approximation of $\frac{1}{\sqrt{b}};$ the second computation comprises determining the second intermediate parameter s.sub.c in accordance with the equation $s_c=\frac{1}{2}\left(3-r_c{p}_c\right);$ and the computation when i=c comprises determining the value of {square root over (b)}, denoted result, in accordance with the equation result=r.sub.cs.sub.c.

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.sub.c; the second computation comprises rounding down to determine the second intermediate parameter s.sub.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.sub.c in accordance with the equation r.sub.c=bp.sub.c where p.sub.c is the previous approximation of $\frac{1}{\sqrt{b}};$ the second computation comprises determining the second intermediate parameter s.sub.c in accordance with the equation $s_c=\frac{1}{2}\left(1-r_c{p}_c\right);$ and the computation when i=c comprises determining the value of {square root over (b)}, denoted result, in accordance with the equation result=r.sub.cs.sub.c+r.sub.c.

17. The computer system of claim 6 further comprising initial approximation logic configured to: obtain the initial approximation of $\frac{1}{\sqrt{b}}$ by: (i) computing the initial approximation of $\frac{1}{\sqrt{b}}$ or (ii) receiving the initial approximation of $\frac{1}{\sqrt{b}};$ and provide the obtained initial approximation of $\frac{1}{\sqrt{b}}$ to the multiplier logic.

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.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Examples will now be described in detail with reference to the accompanying drawings in which:

(2) FIG. 1 is a schematic diagram of a computer system for implementing a square root operation;

(3) FIG. 2 is a flow chart for a method of implementing a square root operation in a computer system; and

(4) FIG. 3 shows a high-level representation of a computer system.

(5) The accompanying drawings illustrate various examples. The skilled person will appreciate that the illustrated element boundaries (e.g., boxes, groups of boxes, or other shapes) in the drawings represent one example of the boundaries. It may be that in some examples, one element may be designed as multiple elements or that multiple elements may be designed as one element. Common reference numerals are used throughout the figures, where appropriate, to indicate similar features.

DETAILED DESCRIPTION

(6) The examples described herein provide a method for finding the result of a square root operation to a desired level of accuracy (i.e. to a desired number of bits of accuracy) using an iterative converging approximation technique which 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 allow a computer system to perform a square root operation with lower latency and with lower power consumption than conventional methods. This can provide a significant benefit, particularly in computer systems which have limited processing resources, e.g. on mobile devices such as smart phones or tablets. It is noted that square root operations are very common in many different computer applications, so even a small improvement in the way in which a computer system can implement a square root operation may provide a significant benefit.

(7) FIG. 1 shows an example of a computer system 100 for implementing a square root operation. The computer system 100 may be implemented in hardware. Implementing the system 100 in hardware may allow for faster computation. The computer system 100 comprises initial approximation logic 102, an iterative converging approximation module 104, and check logic 106. The iterative converging approximation module 104 comprises a control module 108, multiplier logic 110 and a memory 112. In some examples, the logic and modules shown in FIG. 1 are implemented in hardware, e.g. as fixed function circuitry in a computer processor. Each logic block and module shown in FIG. 1 may be implemented as one or more units within the computer system 100. The system 100 is arranged to receive an input value b. In particular, the initial approximation logic 102 is arranged to receive the input value b. An output of the initial approximation logic 102 is coupled to an input of the iterative converging approximation module 104, for providing an initial approximation of

(8) $\frac{1}{\sqrt{b}}$
to the iterative converging approximation module 104. An output of the iterative converging approximation module 104 is coupled to an input of the check logic 106 for providing a determined value of {square root over (b)} to the check logic 106. An output of the check logic 106 is arranged to provide output of the system 100 as the correctly rounded determined value of {square root over (b)}.

(9) The operation of the computer system 100 is described with reference to FIG. 2 which shows a method of implementing a square root operation in the computer system 100. In step S202 an input value b is received at the initial approximation logic 102. In some examples, the system 100 may comprise scaling logic which scales an initial input value by an even power of two such that the input value b received at the initial approximation logic 102 is in the range 1b<4. In those examples, further scaling logic may be provided in the system 100 to scale the output from the check logic 106 to reverse the scaling performed before the input value b is passed to the initial approximation logic 102. For example, if an initial input value is scaled by a factor of to determine the input value b then the determined value of {square root over (b)} output from the check logic 106 is scaled by a factor of 2 to determine the square root of the initial input value. Such scaling and reverse scaling would be apparent to those skilled in the art, and can be implemented such that 1b<4. Since the scaling is by an even power of two then both the scaling and the reverse scaling can be achieved by changing exponents.

(10) The examples described below relate to the Newton Raphson technique, but any other suitable iterative converging approximation technique could be used. As described above, if the Newton Raphson technique is used to determine the zeroes of the function f(x)=bx.sup.2 then, according to equation 5, a division operation would be needed, making the computation not simple to implement in hardware in the computer system 100. So instead, it is noted that

(11) $\sqrt{b}=\frac{b}{\sqrt{b}},$
and the Newton Raphson method can be used to find a value of

(12) $\frac{1}{\sqrt{b}},$
which can then be multiplied by b to thereby find a value of {square root over (b)}. Therefore, in order to implement the Newton Raphson technique, a function f(x) is used whereby

(13) $f\left(\frac{1}{\sqrt{b}}\right)=0.$
There are many functions which could be used, but in the examples described herein, a function

(14) $f\left(x\right)=b-\frac{1}{x^2}$
is used. Therefore,

(15) $f^{}\left(x\right)=\frac{2}{x^3}.$
This means that, in accordance with equation 4 given above, the Newton Raphson method involves computing, on the (i+1).sup.th iteration, an approximation of

(16) 0$\frac{1}{\sqrt{b}},$
denoted p.sub.i+1, according to the equation:

(17) $\begin{array}{cc}{p}_{i+1}=p_i\frac{3-{\mathrm{bp}}_i^2}{2}.& \left(6\right)\end{array}$

(18) So, for example,

(19) $p_1=p_0\left(\frac{3-{\mathrm{bp}}_0^2}{2}\right)$
is a better approximation than p.sub.0 to

(20) $\frac{1}{\sqrt{b}}.$
It is noted that the computations involved in performing an iteration according to equation 6 are simple to implement in a computer system, e.g. they comprise multiplication, subtraction and shifting. The only division involved in an iteration is division by two which can be accomplished (in binary) with a shift instead of a divide, and shift operations are trivial to implement.

(21) Therefore, in step S204 the initial approximation logic 102 computes an initial approximation of

(22) $\frac{1}{\sqrt{b}},$
denoted p.sub.0. There are various approaches which may be used to compute the initial approximation of

(23) $\frac{1}{\sqrt{b}},$
such as a simple table lookup, using parallel table lookups and combining the results, or using a table lookup followed by a multiply to implement an ITY algorithm. For example, the initial approximation p.sub.0 may have at least three bits of accuracy. The initial approximation p.sub.0 is provided to the iterative converging approximation module 104.

(24) In other examples, the system 100 may receive an initial approximation of

(25) $\frac{1}{\sqrt{b}}$
which has been determined outside of the system 100. The initial approximation may in that case be passed to the iterative converging approximation module 104 and there would be no need to implement the initial approximation logic 102 in the system 100. In general, the system 100 obtains an initial approximation of

(26) $\frac{1}{\sqrt{b}}$
(e.g. by either determining it or receiving it), and provides the initial approximation to the iterative converging approximation module 104.

(27) Steps S206 to S218 of the method shown in FIG. 2 are implemented in the iterative converging approximation module 104 in order to determine a value of {square root over (b)}. The multiplier logic 110 may be implemented as a binary multiplier which multiplies numbers together using binary adders, e.g. by computing a set of partial products and then summing the partial products together. It is therefore simple to implement multiply, add, subtract and shift operations in the multiplier logic 110. The control module 108 controls the operation of the iterative converging approximation module 104 so as to perform the iterative converging approximation technique (e.g. the Newton Raphson technique) for determining converging approximations of

(28) $\frac{1}{\sqrt{b}}.$
The memory 112 is used to store values for subsequent use, e.g. to store intermediate parameters and/or to store approximations of

(29) $\frac{1}{\sqrt{b}},$
as will become apparent from the description of the examples below.

(30) In step S206 the iterative converging approximation module 104 (e.g. the control module 108) sets i=0. i is an index, wherein (i+1) denotes the current iteration. The control module 108 keeps track of which iteration is being implemented, and controls the number of iterations which are performed before a value is outputted form the iterative converging approximation module 104.

(31) The iterative converging approximation module 104 receives the input value b and the initial approximation p.sub.0 and stores these values in the memory 112. Each iteration of the iterative converging approximation technique comprises computations including three (and only three in this example) multiplies performed by the multiplier logic 110 of the iterative converging approximation module 104. On each computation, the multiplier logic 110 is capable of performing a multiply operation and/or one or more add/subtract operations and/or a shift operation. On each non-concluding iteration (i.e. where i<c), the iterative converging approximation module 104 determines a value of p.sub.i+1 in accordance with equation 6 using the values of p.sub.i and b. In order to do this, in step S208 a first computation is performed for the current iteration with the multiplier logic 110 to determine a first intermediate parameter, r.sub.i, based on a multiplication of the input value b with the value p.sub.i which is the previous approximation of

(32) 0$\frac{1}{\sqrt{b}}.$
On the first iteration (when i=0) the previous approximation of

(33) $\frac{1}{\sqrt{b}}$
is the initial approximation p.sub.0. As an example, the first intermediate parameter, r.sub.i, may be determined according to the equation:
r.sub.i=bp.sub.i.(7)

(34) The determined value of the first intermediate parameter, r.sub.i, may be stored in the memory 112 for use in subsequent computations.

(35) In step S210 a second computation is performed for the current iteration with the multiplier logic 110 to determine a second intermediate parameter, s.sub.i, based on a multiplication of the first intermediate parameter, r.sub.i, with the value p.sub.i which is the previous approximation of

(36) $\frac{1}{\sqrt{b}}.$
For example, the second intermediate parameter, s.sub.i, may be determined according to the equation:

(37) $\begin{array}{cc}{s}_i=\frac{3-r_i{p}_i}{2}.& \left(8\right)\end{array}$

(38) The determined value of the second intermediate parameter, s.sub.i, may be stored in the memory 112 for use in subsequent computations.

(39) In step S212 it is determined whether the current iteration is a concluding iteration or not, by determining whether i<c. For non-concluding iterations, i.e. where i<c, the method passes to step S214.

(40) In step S214 a third computation is performed for the current iteration with the multiplier logic 110 to determine a refined approximation of

(41) $\frac{1}{\sqrt{b}},$
denoted p.sub.i+1, which is for use in a subsequent iteration, based on a multiplication of the second intermediate parameter, s.sub.i, with the value p.sub.i which is the previous approximation of

(42) $\frac{1}{\sqrt{b}}.$
For example, the refined approximation, p.sub.i+1, may be determined according to the equation:
p.sub.i+1=s.sub.ip.sub.i.(9)
The refined approximation of

(43) $\frac{1}{\sqrt{b}},p_i+1,$
may be stored in the memory 112 for use in subsequent iterations.

(44) It can be appreciated that the three computations shown by the equations 7, 8 and 9 provide the result for p.sub.i+1 in accordance with equation 6, but each of the three computations is suitable for being performed in a binary multiplier of the multiplier logic 110. In particular, binary multipliers are often capable of multiplying two (but not more than two) numbers together in a single computation. Each of the computations performed in steps S208, S210 and S214 comprise multiplying two numbers together. In this example, step S210 also comprises a subtraction and a shift (i.e. a divide by two), but these processes can be approximated after the multiplication performed in that step. Each of the three computations of an iteration may comprise some number of clock cycles (e.g. 3, 4 or 5 clock cycles) to complete.

(45) When a refined approximation, p.sub.i+1, has been determined then, in step S216, a new iteration can be started and the index i is incremented (i.e. i=i+1). The method then passes back to step S208 and the method proceeds from that point as described above.

(46) The control module 108 determines the number of iterations that are to be performed and sets the value of c to reflect this. As an example, the control module 108 may control the number of iterations of the iterative converging approximation technique which are to be performed based on: (i) the number of bits of accuracy of the initial approximation of

(47) $\frac{1}{\sqrt{b}},p_0,$
and (ii) a desired number of bits of accuracy of the determined value of {square root over (b)}.

(48) The Newton-Raphson method of finding the reciprocal square root, using the above equations, provides a convergence that is quadratic. That is, each iteration approximately doubles the accuracy of the approximation. This can be seen as follows. An approximation p.sub.i is not an exact result, so

(49) $p_i\frac{1}{\sqrt{b}},$
and instead there is some error, .sub.i, in the approximation such that

(50) $p_i+{\mathrm{.Math.}}_i=\frac{1}{\sqrt{b}}.$
The error, .sub.i, may be positive or negative. Therefore p.sub.i, can be written as:

(51) 0$\begin{array}{cc}{p}_i=\frac{1}{\sqrt{b}}-{\mathrm{.Math.}}_i.& \left(10\right)\end{array}$

(52) From equation 10 and equations 7, 8 and 9, it follows that:

(53) $\begin{array}{cc}{r}_i=\sqrt{b}-{\mathrm{.Math.}}_{i}b.& \left(11\right)\\ s_i=1+{\mathrm{.Math.}}_i\sqrt{b}-\frac{{\mathrm{.Math.}}_i^{2}b}{2}.& \left(12\right)\\ p_{i+1}=\frac{1}{\sqrt{b}}-\frac{{\mathrm{.Math.}}_i^2\sqrt{b}}{2}\left(3-{\mathrm{.Math.}}_i\sqrt{b}\right).& \left(13\right)\end{array}$

(54) As described above, a scaling operation may be performed such that 1b<4, and a good initial approximation is assumed such that the approximation p.sub.0 has at least three bits of accuracy such that |.sub.0|<2.sup.3. Therefore, (3.sub.i{square root over (b)}) is positive, and so is

(55) $\frac{{\mathrm{.Math.}}_i^2\sqrt{b}}{2}.$
Therefore,

(56) $p_{i+1}<\frac{1}{\sqrt{b}}.$
It is useful to ensure that the approximations of

(57) $\frac{1}{\sqrt{b}}$
are not larger than the true value of

(58) $\frac{1}{\sqrt{b}},$
because a check procedure performed by the check logic 106 (described below with reference to step S220) may rely on an assumption that the determined value for {square root over (b)} is less than the true value of {square root over (b)} in order to check that the value for {square root over (b)} is correctly rounded. The error .sub.i+1 in the approximation p.sub.i+1 is given by:

(59) ${\mathrm{.Math.}}_{i+1}=\frac{{\mathrm{.Math.}}_i^2\sqrt{b}}{2}\left(3-{\mathrm{.Math.}}_i\sqrt{b}\right).$

(60) Since p.sub.i+1 differs from

(61) $\frac{1}{\sqrt{b}}$
by about .sub.i.sup.2 (whereas p.sub.i differs from

(62) $\frac{1}{\sqrt{b}}$
by .sub.i) it can be appreciated that p.sub.i+1 has about twice as many bits of accuracy as p.sub.i. For example, if the initial approximation, p.sub.0, has 7 bits of accuracy, then p.sub.i would have about 14 bits of accuracy, p.sub.2 would have about 28 bits of accuracy (enough for single precision floating point), and p.sub.3 would have about 56 bits of accuracy (enough for double precision floating point).

(63) As an example, the control module 108 may determine that the desired result is a single precision floating point number, for which at least 24 bits of accuracy are desired, and that the initial approximation, p.sub.0, has 7 bits of accuracy. In that case, the controller sets c=1, such that two iterations are performed, and therefore in a simple example six computations may be performed to determine p.sub.2. In this simple example, at the end of the second iteration the value of p.sub.2 could be multiplied by b in order to determine a value of {square root over (b)}, i.e. result=bp.sub.2, such that seven computations are performed to determine a value of {square root over (b)}.

(64) As another example, the control module 108 may determine that the desired result is a double precision floating point number, for which at least 53 bits of accuracy are desired, and that the initial approximation, p.sub.0, has 7 bits of accuracy. In that case, the controller sets c=2, such that three iterations are performed, and therefore in a simple example nine computations may be performed to determine p.sub.3. In this simple example, at the end of the third iteration the value of p.sub.3 could be multiplied by b in order to determine a value of {square root over (b)}, i.e. result=bp.sub.3, such that ten computations are performed to determine a value of {square root over (b)}.

(65) However, the number of computations performed to determine a value of {square root over (b)} can be reduced compared to the simple examples described in the two preceding paragraphs. This is achieved by implementing the concluding iteration without determining a refined approximation of

(66) $\frac{1}{\sqrt{b}}$
on the concluding iteration.

(67) On the final iteration, i.e. the concluding iteration, then the control module 108 has set c such that i=c. Steps S208 and S210 are performed as above in accordance with equations 7 and 8. That is, in step S208 on the final iteration, the first computation is performed with the multiplier logic 110 to determine a first intermediate parameter r.sub.c for the concluding iteration based on a multiplication of the input value b with a previous approximation of

(68) 0$\frac{1}{\sqrt{b}},$
i.e. p.sub.c. For example the first intermediate parameter r.sub.c for the concluding iteration may be given by the equation:
r.sub.c=bp.sub.c.(14)

(69) Furthermore, in step S210 on the final iteration, the second computation is performed with the multiplier logic 110 to determine a second intermediate parameter s.sub.c for the concluding iteration based on a multiplication of the first intermediate parameter r.sub.c for the concluding iteration with the previous approximation of

(70) $\frac{1}{\sqrt{b}},$
i.e. p.sub.c. For example the second intermediate parameter s.sub.c for the concluding iteration may be given by the equation:

(71) $\begin{array}{cc}{s}_c=\frac{3-r_c{p}_c}{2}.& \left(15\right)\end{array}$

(72) Then in step S212 it is determined that i is not less than c because this is the final iteration so i=c. Therefore the method passes from step S212 to step S218. In step S218, instead of determining a refined approximation of

(73) $\frac{1}{\sqrt{b}},$
i.e. p.sub.c+1, a concluding computation is performed with the multiplier logic 110 to determine the value of {square root over (b)} based on a multiplication of the first intermediate parameter r.sub.c for the concluding iteration with the second intermediate parameter s.sub.c for the concluding iteration. For example the value of {square root over (b)} (denoted result) may be determined according to the equation:
result=r.sub.cs.sub.c.(16)

(74) In this way, the two steps from the simple example described above of: (i) determining p.sub.c+1 as p.sub.c+1=s.sub.cp.sub.c, and then (ii) determining the result as result=bp.sub.c+1, are reduced into one step as given by equation 16. The following equation shows that this reduction is valid:
result=bp.sub.c+1=bs.sub.cp.sub.c=bp.sub.cs.sub.c=r.sub.cs.sub.c.(17)

(75) Reducing the number of computations which are performed in the final iteration can provide a significant benefit. Each computation takes a number of clock cycles (e.g. 3, 4 or 5 clock cycles) to be performed. So reducing the number of computations that are performed on the final iteration reduces the time taken to determine the value of {square root over (b)}. This means that the latency is reduced, i.e. the result can be provided sooner. Furthermore, reducing the number of computations which are performed reduces the power that is consumed to determine the value of {square root over (b)}.

(76) The value of {square root over (b)} determined in step S218 is outputted from the iterative converging approximation module 104 to the check logic 106. In step S220, the check logic 106 may 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. The rounding mode may for example be a round up mode, a round down mode or a round to nearest mode. Details of the check procedure performed by the check logic 106 are beyond the scope of this disclosure, but it is noted that the check procedure may rely on an assumption that the determined value of {square root over (b)} is not greater than the exactly correct value of {square root over (b)}. The output from the check logic 106 is either the same as the value of {square root over (b)} received from the iterative converging approximation module 104 or is that value incremented by one unit of least precision (ULP) (i.e. the value of {square root over (b)} received from the iterative converging approximation module 104 with the least significant digit incremented by one).

(77) In step S222 the resulting value for {square root over (b)} is outputted from the check logic 106 as the output of the computer system 100. The outputted value of {square root over (b)} may be put to any suitable use after it has been outputted, e.g. stored in a memory or used in subsequent computations, etc.

(78) In some examples, the check logic 106 might not be implemented in the system 100. That is, the check procedure might not be performed in some examples. In those examples, the value of {square root over (b)} determined by the iterative converging approximation module 104 is outputted from the system 100 and used to represent the value of {square root over (b)}.

(79) The accuracy of the iterations is now considered. The multiplier logic 110 may be configured to take two k-bit values as input and provide a 2k-bit result. For example, if b and p.sub.i both have k bits then in the first computation when bp.sub.i is computed, the result r.sub.i has twice as many bits (2k) as each of the inputs. However, when r.sub.i is used as an input to the next computation in computing r.sub.ip.sub.i, it may only contain k bits. So, the k least significant bits of r.sub.i are removed and the k most significant bits are rounded up or down before being used in the next computation. This rounding may introduce additional error terms. In particular, the first intermediate parameter r.sub.i has an error, , introduced by rounding, such that equation 11 becomes:
r.sub.i={square root over (r)}.sub.ib+.(18)

(80) In order to round r.sub.i up, would be positive; and in order to round r.sub.i down, would be negative. The second intermediate parameter s.sub.i has an error, , introduced by rounding, and using equations 8, 10 and 18, s.sub.i is given by:

(81) $\begin{array}{cc}{s}_i=\frac{3-r_i{p}_i}{2}+=\frac{3-\left(\sqrt{b}-{\mathrm{.Math.}}_{i}b+\right)\left(\frac{1}{\sqrt{b}}-{\mathrm{.Math.}}_i\right)}{2}+=1+{\mathrm{.Math.}}_i\sqrt{b}-\frac{{\mathrm{.Math.}}_i^{2}b}{2}-\frac{}{2}\left(\frac{1}{\sqrt{b}}-{\mathrm{.Math.}}_i\right)+.& \left(19\right)\end{array}$
In order to round s.sub.i up, would be positive; and in order to round s.sub.i down, would be negative.

(82) On the concluding iteration, the determined value for {square root over (b)} is computed with an error, , introduced by rounding. Using equations 16, 18 and 19 result is given by:

(83) $\begin{array}{cc}\mathrm{result}=r_c{s}_c+\mathrm{result}=\left(\sqrt{b}-{\mathrm{.Math.}}_{c}b+\right)\left(1+{\mathrm{.Math.}}_c\sqrt{b}-\frac{{\mathrm{.Math.}}_c^{2}b}{2}-\frac{}{2}\left(\frac{1}{\sqrt{b}}-{\mathrm{.Math.}}_c\right)+\right)+\mathrm{result}=\sqrt{b}+{\mathrm{.Math.}}_{c}b-\frac{{\mathrm{.Math.}}_c^{2}b\sqrt{b}}{2}-\frac{}{2}+\frac{{\mathrm{.Math.}}_c\sqrt{b}}{2}+\sqrt{b}-{\mathrm{.Math.}}_{c}b-{\mathrm{.Math.}}_c^{2}b\sqrt{b}+\frac{{\mathrm{.Math.}}_c^3{b}^2}{2}+\frac{{\mathrm{.Math.}}_c\sqrt{b}}{2}-\frac{{\mathrm{.Math.}}_c^{2}b}{2}-{\mathrm{.Math.}}_{c}b++{\mathrm{.Math.}}_c\sqrt{b}-\frac{{\mathrm{.Math.}}_c^{2}b}{2}-\frac{{}^2}{2\sqrt{b}}+\frac{{}^2{\mathrm{.Math.}}_c}{2}++\mathrm{result}=\sqrt{b}-\frac{{\mathrm{.Math.}}_c^{2}b\sqrt{b}}{2}\left(3-{\mathrm{.Math.}}_c\sqrt{b}\right)+\left(\frac{1}{2}-\frac{}{2\sqrt{b}}+{\mathrm{.Math.}}_{c}b\left(\frac{2}{\sqrt{b}}-{\mathrm{.Math.}}_c\right)+\frac{{\mathrm{.Math.}}_c}{2}\right)+\left(\sqrt{b}+-{\mathrm{.Math.}}_{c}b\right)+& \left(20\right)\end{array}$

(84) As described above, for the check procedure to work correctly, the result should not be greater than {square root over (b)}. To ensure this, on the final iteration, r.sub.c, s.sub.c and result are rounded down, i.e. , and are set to be negative. On non-concluding iterations the rounding of, r.sub.i, s.sub.i and p.sub.i+1 does not need to be constrained to any particular rounding mode, but it may be simpler to use a round down mode since this is used on the concluding iteration. On the concluding iteration, the error .sub.c is small because this is the error in the previous approximation p.sub.c. For example, for a single precision result, on the final iteration, |.sub.c|<2.sup.24 and for a double precision result, on the final iteration, |.sub.c|<2.sup.53. Also since and are rounding errors, they have a similar magnitude to .sub.c, so for a single precision result, on the final iteration, 0>2.sup.24 and 0>2.sup.24, and for a double precision result, on the final iteration, 0>2.sup.53 and 0>2.sup.53. Furthermore, as described above, 1b<4, such that 1{square root over (b)}<2. Therefore each term in equation 20 after {square root over (b)} is negative since , and .sub.c are all tiny compared to 3, and {square root over (b)}. Therefore, the result determined in equation 20 is smaller than {square root over (b)} such that it is suitable for the check procedure. This is true irrespective of whether .sub.c is positive or negative, which is why it is not important to constrain the rounding performed in the non-concluding iterations.

(85) In the examples described above, on non-concluding iterations, a refined approximation p.sub.i+1 is determined according to equation 6 using the three computations as set out in equations 7 to 9. In an alternative method, in step S208, the first computation is performed in the same way as described above for a current iteration with the multiplier logic 110. That is, a first intermediate parameter, r.sub.i, may be determined according to the equation:
r.sub.i=bp.sub.i.(21)

(86) The determined value of the first intermediate parameter, r.sub.i, may be stored in the memory 112 for use in subsequent computations.

(87) In the alternative method, in step S210, as described above, a second computation is performed for the current iteration with the multiplier logic 110 to determine a second intermediate parameter, s.sub.i, based on a multiplication of the first intermediate parameter, r.sub.i with the value p.sub.i which is the previous approximation of

(88) $\frac{1}{\sqrt{b}}.$
However, in contrast to equation 8 given above, in the alternative method the second intermediate parameter, s.sub.i, may be determined according to the equation:

(89) $\begin{array}{cc}{s}_i=\frac{1-r_i{p}_i}{2}.& \left(22\right)\end{array}$

(90) The determined value of the second intermediate parameter, s.sub.i, may be stored in the memory 112 for use in subsequent computations.

(91) Then for non-concluding iterations, in step S214, a third computation is performed for the current iteration with the multiplier logic 110 to determine a refined approximation of

(92) $\frac{1}{\sqrt{b}},$
denoted p.sub.i+1, which is for use in a subsequent iteration, based on a multiplication of the second intermediate parameter, s.sub.i, with the value p.sub.i which is the previous approximation of

(93) $\frac{1}{\sqrt{b}}.$
In an alternative method, the refined approximation, p.sub.i+1, may be determined according to the equation:
p.sub.i+1=s.sub.ip.sub.i+p.sub.i.(23)
The refined approximation of

(94) 0$\frac{1}{\sqrt{b}},p_{i+1},$
may be stored in the memory 112 for use in subsequent iterations.

(95) For concluding iterations, in step S218, a concluding computation is performed with the multiplier logic 110 to determine the value of {square root over (b)} based on a multiplication of the first intermediate parameter r.sub.c for the concluding iteration with the second intermediate parameter s.sub.c for the concluding iteration. In the alternative method, the result may be determined according to the equation:
result=r.sub.cs.sub.c+r.sub.c.(24)

(96) This alternative method has the same advantages as the method described in detail above. In particular, the final iteration avoids a computation to determine a refined approximation of

(97) $\frac{1}{\sqrt{b}}.$
As described above, reducing the number of computations that are performed on the final iteration has benefits in terms of the power consumption and latency of the system 100 in determining the value of {square root over (b)}.

(98) By way of explanation, equation 24 has the same result as performing two computations: (i) determining p.sub.c+1 as p.sub.c+1=s.sub.cp.sub.c+p.sub.c, and then (ii) determining the result as result=bp.sub.c+1. This is shown in the following equation:
result=bp.sub.c+1=bs.sub.cp.sub.c+bp.sub.c=r.sub.cs.sub.c+r.sub.c.(25)

(99) In the alternative method, all operations typically use fused multiply-add operations with the requested rounding mode for the final result, in which case no check procedure is needed.

(100) In the examples described above, a plurality of iterations of the iterative converging approximation technique are performed (i.e. c1), such that a refined approximation of

(101) $\frac{1}{\sqrt{b}}$
determined in the iteration preceding the final iteration is used as a previous approximation of

(102) $\frac{1}{\sqrt{b}}$
in the concluding iteration. However, in other examples, only one iteration of the iterative converging approximation technique may be performed, such that the first iteration is the concluding iteration (i.e. c=0) and the initial approximation of

(103) $\frac{1}{\sqrt{b}}$
is used as the previous approximation of

(104) $\frac{1}{\sqrt{b}}$
in the concluding iteration.

(105) The computing system 100 described above with reference to FIG. 1 can be implemented as a unit at a processor in a larger computer system. For example, FIG. 3 shows a larger computer system 300 which comprises a processor 302 on which the system 100 is implemented. The processor 302 is a central processing unit (CPU). In the example shown in FIG. 3, the computer system 300 also comprises a memory 304, a graphics processing unit (GPU) 306 and other devices 308, such as a display 310, speakers 312, a microphone 314 and a keypad 316. The components of the computer system 300 can communicate with each other via a communications bus 318. In other examples, the system 100 may be implemented as a unit on the GPU 306 as well as or instead of being implemented as a unit on the CPU 302. When a square root operation is to be performed, an input value b can be provided to the unit 100 and the unit 100 operates as described above to output a value of {square root over (b)}, which can then be used in the system 300 as appropriate.

(106) Examples are described above, by way of example only, of a computer system which is configured to implement a square root operation using an iterative converging approximation technique in a manner which has low latency and low power consumption. For example, the number of computations is lower than might be expected. This results in a faster method which uses less power than conventional methods, and the method may be implemented in hardware which is smaller and simpler to implement than conventional hardware for implementing square root operations.

(107) The terms module, block and logic are used herein to generally represent hardware, including fixed function hardware, configurable hardware, programmable hardware, and combinations thereof. Firmware, software, or some combination thereof can be used to configure and/or program such hardware.

(108) In one example, the methods described may be performed by a computer configured with software in machine readable form stored on a computer-readable medium. The computer-readable medium may be configured as a non-transitory computer-readable storage medium and thus is not a signal bearing medium. Examples of a computer-readable storage medium include a random-access memory (RAM), read-only memory (ROM), an optical disc, flash memory, hard disk memory, and other memory devices that may use magnetic, optical, and other techniques to store instructions or other data and that can be accessed by a machine.

(109) The software may be in the form of a computer program comprising computer program code. The program code can be stored in one or more computer readable media. The features of the techniques described herein are platform-independent, meaning that the techniques may be implemented on a variety of computing platforms having a variety of processors.

(110) Those skilled in the art will realize that all, or a portion of the functionality, techniques, logic or methods may be carried out by a dedicated circuit, an application-specific integrated circuit, a programmable logic array, a field-programmable gate array, or the like. For example, the module, block, unit or logic may comprise hardware in the form of circuitry. Such circuitry may include transistors and/or other hardware elements available in a manufacturing process. Such transistors and/or other elements may be used to form circuitry or structures that implement and/or contain memory, such as registers, flip flops, or latches, logical operators, such as Boolean operations, mathematical operators, such as adders, multipliers, or shifters, and interconnects, by way of example. Such elements may be provided as custom circuits or standard cell libraries, macros, or at other levels of abstraction. Such elements may be interconnected in a specific arrangement. The module, block, unit or logic (e.g. the components shown in FIG. 1) may include circuitry that is fixed function and circuitry that can be programmed to perform a function or functions; such programming may be provided from a firmware or software update or control mechanism. In an example, hardware logic has circuitry that implements a fixed function operation, state machine or process.

(111) It is also intended to encompass software which describes or defines the configuration of hardware that implements a module, block, unit or logic described above, such as HDL (hardware description language) software, as is used for designing integrated circuits, or for configuring programmable chips, to carry out desired functions. That is, there may be provided a computer readable storage medium having encoded thereon computer readable program code for generating a computer system (e.g. computer hardware) configured to perform any of the methods described herein, or for generating a computer system (e.g. computer hardware) comprising any apparatus described herein. One such configuration of a computer-readable medium is signal bearing medium and thus is configured to transmit the instructions (e.g. as a carrier wave) to the computing device, such as via a network. The computer-readable medium may also be configured as a non-transitory computer-readable storage medium and thus is not a signal bearing medium. Examples of a computer-readable storage medium include a random-access memory (RAM), read-only memory (ROM), an optical disc, flash memory, hard disk memory, and other memory devices that may use magnetic, optical, and other techniques to store instructions or other data and that can be accessed by a machine.

(112) The term processor and computer are used herein to refer to any device, or portion thereof, with processing capability such that it can execute instructions, or a dedicated circuit capable of carrying out all or a portion of the functionality or methods, or any combination thereof.

(113) Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims. It will be understood that the benefits and advantages described above may relate to one example or may relate to several examples.

(114) Any range or value given herein may be extended or altered without losing the effect sought, as will be apparent to the skilled person. The steps of the methods described herein may be carried out in any suitable order, or simultaneously where appropriate. Aspects of any of the examples described above may be combined with aspects of any of the other examples described to form further examples without losing the effect sought.