General Description: This Answer Record contains information regarding CORE Generator 4K Square Root module implementation.
The implementation of the Square Root module is best illustrated with an example, which will use the square root of 121 (decimal):
121 in binary = 01111001
1. The binary value is broken up into groups of two digits: 01 11 10 01.
2. Find a number for which the square root is equal to the first two (MSB) digits on the left. In this case, the square root of 1 = 01; therefore, 1 is the MSB of the result.
3. Subtract 1 from the first two digits, and bring the next two digits down. We now have the following number: 011
4. The second bit of the result must satisfy the following: 10n x n <= 011. (The "10" of "10n" is the result of taking the MSB of the Square Root output, shifting it left, and padding it with a 0.)
In this case, n=0 : 100 x 0 = 0 <= 011.
(If we had used n=1, we would have gotten 101 x 1 = 101, which is greater than 011.)
We now have the second bit of the result, 0, giving us a partial result of 10.
5. Because n was 0, subtract 0 x 100=000 from 011, and bring the next two digits (10) down. This gives us 01110.
6. The third bit of the result must satisfy the following: 100n x n <= 01110, where 100 is obtained by taking the partial result of 10, shifting it left, and padding it with a 0.
In this case n=1, as 1001 x 1 = 1001 <= 01110
We now have the third bit of the result, 1, giving a partial result of 101.
7. Subtract 1001 from 01110 (01110 - 01001 = 00101) and bring the last two digits (01) down. We now have the following number: 010101
8. The fourth bit of the result must satisfy the following: 1010n x n <= 010101, where 101 is obtained by taking the partial result, shifting it left, and padding it with a 0.
In this case n=1: 10101 x 1 = 10101 <= 010101 We now have the fourth bit of the result, giving us a partial result of 1011 .
9. Subtract 10101 from 010101. The difference is 0, so the final result is 1011 (11 in decimal), which is in agreement: sqrt(121) = 11
If the difference for this last subtraction was not 0, we could keep bringing 0s down and continuing the operation. The precision of the result will depend upon the number of bits requested for the output.