GB2199430A - Square root determining device - Google Patents

Abstract

A digital device is provided for implementing an iterative algorithm for determining the square root of a binary number, which comprises a plurality of similar cells 10 each performing an iteration of the algorithm in which the number is compared, two additional bits at a time, starting from the most significant bit (MSB), with the function 2R+1 of an initially zero, progressively increasing estimate R of the square root and, if greater than the function, a one is added (at 32, 20a) to the estimate of the square root and the compared bits of the number are reduced (at 26, 30) by the function. <IMAGE>

Description

DIGITAL DEVICE This invention concerns a digital device, and in particular a device for determining the square root of a number. The device implements an algorithm requiring a number of iterations in which an estimate of the square root is progressively formed. The algorithm is implemented in a "straight through" device in which each iteration is effected by a cell.

An object of the present invention is the provision of an improved device for determining the square root of a number.

According to the present invention, there is provided a digital device for implementing an algorithm determining the square root of a binary number, comprising n cells where n is the number of iterations performed, a first path whereon a binary number, the square-root of which is to be determined, is fed, a second path whereon an estimate R in binary form of the square root is progressively formed, the first and second paths connecting and passing .through each of the cells, and wherein each cell includes a two-bit shift left of the first path and a one-bit shift left of the second path, means for determining the function 2R+1, means (a) for comparing the determined function with the number on the firs path, (b) for subtractng the function from the number on the first path if said number is greater than the function and for substituting, for the number, the result of the subtraction, on the first path, and (c) for increasing the value of the estimate R on the second path by one, if said number is greater than the function.

Registers may be included between each adjacent pair of cells for temporarily storing the numbers appearing on the first and second paths. The shift lefts may be effected by hard wire connections between the registers and the continuations of the first and second paths.

The comparing means may generate a sign bit when the said number is greater than the function and means may be provided for effecting the substitution and for increasing the value of the estimate R in dependence upon the generated sign bit.

The substitution effecting means may comprise a multiplexer controlled by the sign bit to effect substitution if the number is greater than the function, and to pass the number unchanged along the first path if the number is not greater than the function.

The means for increasing the value of the estimate R by one comprises an inverter responsive to the sign bit for adding one to the least significant bit (LSB) of the second path if the number is greater than the function and to pass the estimate R unchanged along the second path if the number is not greaser than the function.

The width of the second path may be n bits.

The width of the first path may be as wide as the binary number whose square is to be determined.

The device of the invention is very simple and regular and consequently it is eminently suitable for fabrication by integrated circuit technology.

The invention will be described further, by way of example, with reference to the accompanying drawings, in which: Figure 1 is a flow chart illustrating the algorithm implemented by the device according to the present invention; and Figure 2 is a block schematic diagram of one cell of a straight through device, having a plurality of such cells, according to the present invention.

Referring firstly to Figure 1, this depicts an algorithm for calculating the square root of a binary number X, in which the best estimate R of the square root is progressively formed and n iterations of the loop in the algorithm are necessary to produce an estimate R, n bits wide.

Initially, a Result register R and a High register H are cleared, and a count C-l determining the number of iterations (and the number of cells in the implementation) is loaded. The number X is loaded into a Low register L of the High regiser plus Low register pair (HL). HL is shifted left two bits and the Result register R is shifted left one bit. A function (2R+1) is calculated and compared with the contents of the H register. If the contents of the H register are less than the function, the count is decremented, compared with zero and looped to again perform the shift left operations.

If the contents of the H register are greater than the function, the contents of the H register are replaced by the result of the subtraction of the function from the contents of the H register, the estimate of the square root R is increased by one, the count is decremented and compared to zero and looped to again perform the shift left operations.

Wen the count is equal to zero, the best estimate R of the square root is the binary number appearing in the R register.

In order to avoid the repetitive use of the same registers and to facilitate VLSI implementations, the device according to the invention comprises a plurality of serially connected cells, each cell constituting one iteration of the algorithm loop.

As shown in Figure 2 of the drawings each cell 10 of the plurality of cells forming the device comprises a first path 12 defined by an internal bus structure including the H and L registers 14, 16 which path serially connects and passes through each of the cells of the device. A second path 18 formed by an internal bus structure including the register R (register 20) which serially connects and passes through each of the cells of the device.

The first path 12 is hard wired to effect a two bit left shift and the second path 18 is similarly wired to effect a one bit left shift.

Thereafter, the value on the second path is doubled (left shifted once) in the multiplier 22, has one added thereto in the adder 24 and the resulting function 2R+1 is compared in a comparator 26 with the number in the H register. If the function 2R+l is less than the number in the H register, then a sign bit is generated at 28 and is used to control a multiplexer 30 which then substitutes the result of a subtraction H-2R+1 into the H register 14a of the next cell. The sign bit is also inverted by an inverter 32 and added to the least significant bit (LSB) of the R register 20a of the next cell.

The multiplexer 30 is controlled so as to pass the number in the H register 14 to the H register 14a of the next cell unchanged. Similarly, the estimate R of the square root is passed unchanged from the register 20 to the register 20a of the next cell if the contents of the H register are less than or equal to the function.

The decremented count function is implemented in the device by providing a number of the cells 10 to equal the desired number of iterations. In this respect the width of the second path 18 is equal to the number of cells as a bit value of R may be generated in each cell.

It will be noted that the data bits on the path 12 are only as wide as the width of the initial L register 16. The initial contents of the first H register 14 are zero and, upon progressive two bit left shifts to fill the subsequent registers 14a..., the width of data bits in subsequent L registers 16a..., decreases an equivalent amount. Thus, the arrangement of registers 14 and 16 can be realised by a single register of width equal to the register 16 interposed on the first path 12 between each pair of cells.

As the structure of each cell of the device is very simple and regular, the device can readily be fabricated as an integrated circuit using VLSI techniques. Its straight-through configuration can enable a very high through-put speed. The number of cells, and hence the c,utput word size, the square root, can be increased or decreased easily during manufacture.

The device of the invention may be readily incorporated into any digital processing apparatus where a requirement to determine square roots exists.

The invention is not confined to the precise details of the foregoing example and variations may be made thereto as will readily be apparent to those skilled in the art.

Claims (9)

CLAIMS:

1. A digital device for implementing an algorithm determining the square root of a binary number, comprising n cells where n is the number of iterations performed, a first path whereon a binary number, the square-root of which is to be determined, is fed, a second path wherein an estimate R in binary form of the square root is progressively formed, the first and second paths connecting and passing through each of the cells, and wherein each cell includes a two-bit shift left of the first path and a one-bit shift left of the second path, means for determining the functions 2R+1, means (a) for comparing the determined function with the number on the first path, (b) for subtracting the function from the number on the first path if said number is greater than the function and for substituting, for the number, the result of the subtraction, on the first path, and (c) for increasing the value of the estimate R on the second path by one, if said number is greater than the function.

2. A device as claimed in Claim 1, wherein registers are included between each adjacent pair of cells for temporarily storing the numbers appearing on the first and second paths.

3. A device as claimed in Claim 1 or 2, wherein the shift lefts are effected by hard wire connections between the registers and the continuations of the first and second paths.

4. A device as claimed in Claim 1, 2 or 3, wherein the comparing means generates a sign bit when said number is greater than the function and means are provided for effecting the substitution and for increasing the value of the estimate R in dependence upon the generated sign bit.

5. A device as claimed in Claim 4, wherein the substitution effecting means comprises a multiplexer controlled by the sign bit to effect substitution if the number is greater than the function, and to pass the number unchanged along the first path if the number is not greater than the function.

6. A device as claimed in Claim 4 or 5, wherein the means for increasing the value of the estimate R by one comprises an inverter responsive to the sign bit for adding one to the least significant bit (LSB) of the second path if the number is greater than the function and to pass the estimate R unchanged along the second path if the number is not greater than the function.

7. A device as claimed in any preceding claim wherein the width of the second path is n bits.

8. A device as claimed in any preceding claim wherein the width of the first path is as wide as the binary number whose square-root is to be determined.

9. A digital device substantially as hereinbefore described, with reference to and as illustrated in the accompanying drawings.