Square root calculations on an associative processing unit

1. A method for calculating a square root B having N bits of a number X having 2N bits, the method comprising:

iterating on bits b i of said square root B starting from the most significant bit until the least significant bit of square root B and for each iteration i, performing the following;

locating a 1 at a squared location of the ith bit in a CHECK variable stored in a row of a memory array, said CHECK variable storing previously determined bits;

determining a value of bit b i from a result of a difference between a remainder from a previous difference and said CHECK variable;

in said row, shifting all previously determined bits right 1 location in said CHECK variable; and

adding the determined value of bit b i into its squared location in said CHECK variable.

2. The method according to claim 1 wherein said CHECK variable is of length 2N and, wherein said determining a value of bit b i uses only a relevant portion of said CHECK variable.

3. The method according to claim 1 wherein, in said locating, said squared location is two bits to the right of the current locations of all previously determined bits in said CHECK variable.

4. The method according to claim 1 wherein said adding is implemented as an OR operation.

5. The method according to claim 1 which is implemented on an associative memory device.

6. The method according to claim 1 which is implemented on a central processing unit (CPU).

7. A square root calculator for calculating a square root B having N bits of a number X having 2N bits, the calculator comprising:

a central processing unit (CPU) and;

a memory array having a plurality of memory cells organized into rows and columns, the memory array having one row for a CHECK variable and a second row for a PREV variable, said PREV variable being aligned with said CHECK variable;

said CPU to iterate on bits b i of said square root B starting from the most significant bit until the least significant bit of square root B and, for each iteration, said CPU to:

locate a 1 at a squared location the ith bit in said row of said CHECK variable, said CHECK variable storing previously determined bits;

determine a value of bit b i from a result of a difference between said PREV variable, storing a remainder from a previous difference, and said CHECK variable;

shift all previously determined bits right 1 location in said row of said CHECK variable; and

add the determined value of bit b i into its squared location in said CHECK variable.

8. The calculator according to claim 7 wherein said CHECK variable is of length 2N and, wherein said CPU uses only a relevant portion of said CHECK variable.

9. The calculator according to claim 7 wherein said squared location is two bits to the right of the current locations of all previously determined bits in said CHECK variable.

10. A square root calculator for calculating a square root B having N bits of a number X having 2N bits, the calculator comprising:

an associative processing unit (APU), said APU comprising:

a memory array having a plurality of memory cells organized into rows and columns, the memory array having one row for a CHECK variable and a second row for a PREV variable, said PREV variable being aligned with said CHECK variable;

a multiple row decoder to activate multiple rows at a time; and

a controller to activate said multiple row decoder to iterate on bits b i of said square root B starting from the most significant bit until the least significant bit of square root B and, for each iteration, said controller to instruct the following operations:

writing a 1 at a squared location of the ith bit in said CHECK variable, said CHECK variable storing previously determined bits;

determining a value of bit b i from a result of a difference between said PREV variable, storing a remainder from a previous difference, and said CHECK variable;

shifting all previously determined bits right 1 location in said CHECK variable; and

OR'ing the determined value of bit b i in its squared location with said CHECK variable.

11. The calculator according to claim 10 wherein said CHECK variable is of length 2N and, wherein said OR'ing uses only a relevant portion of said CHECK variable.

12. The calculator according to claim 10 wherein said squared location is two bits to the right of the current locations of all previously determined bits in said CHECK variable.