Minimum requirements for your design:

• It must be implemented on the MAX 7128SLC84 or the FLEX 10K device of the Altera University Demo boards  (Max 7000  data sheet) (FLEX 10K data sheet)
• It must generate the correct integer result and display it in hex until a new number is input.
• It must be well documented in a design report.
• It must be presented in class by your team.

• Maximize the number of bits in the input. Note that there are only 16 switches on the University board for the MAX part, and only 8 for the FLEX 10K part, so larger inputs must be input sequentially.
• Document in your report that more than one design (at the ASM chart level) was considered and you chose a design that optimized speed or area.
• Represent the result in decimal.

To find the square root of N:

root <- 0
for i in  MSB-position of root downto 0
        set bit i of root
        if root*root > N then
                reset bit i

Here is a C program that implements this algorithm. It is only provided as an executable specification that might help a little to understand the alogorithm.  You should not try to implement it directly in VHDL.

Note that the algorithm includes a multiplication.

1. Store each root and root^2 as it is generated. The initial values are known.

The new (root') and old root values are related as follows:   root'  =  root  +  x   where x is a power of 2.

To find root' * root' we can substitute (root + x) and get

(root + x ) (root + x)

Multiplying this out we get:

root^2  +  2 x root + x^2

The first term is the value of the last root^2, which we have stored.
The second term is a multiplication by a power of 2, so can be accomplished by shifting.
The third term is also a multiplication by a power of 2, so can be accomplished by shifting.
Notice that the number of bits shifted is related to the loop index variable.

A C program that uses the shift and add rather than the multiplication is also given, and the same warnings apply.

loop for (input bitsize)/2 times
    double left shift input into working_reg
    copy 2*root to temp
    shift a 1 into rightmost bit of root 
    shift a 1 into rightmost bit of temp
    is temp > working_reg?
       yes, invert last bit of root
       no, working_reg :=  working_reg - temp

In this algorithm, the input is considered 2 bits at a time, starting from the left. The working register initially contains the first two bits, and later may contain a remainder that must be considered in the next iteration. Here is an example in decimal of the manual method from which the algorithm is derived:

input: 341642
temp
 |
            341642    |  584   <-- root
 5          25     <----- 5 * 5
            ------
             916
108          864   <----- 8 * 108
            ------
              5242
1164          4656 <----- 4 * 1164
            ------
               586 <---- remainder

Note that the first root value, 5, must be guessed. The 10 in 108 is twice the initial root value. The 116 in 1164 is twice the second root value, 58.

Now for an example in binary:

input: 10011111
initial root guess is 1
root = 0001

temp
|
        10011111   | 1100     <---- root value grown msb first
1        1    <--- initial root value for first loop
        --------
        0101  <--- working register after second loop
101      101
        --------
1100       011 <--- working register after third loop
           000
        --------
11000       1111 <--- working register after fourth loop
            0000
            1111  <---- remainder left in working register

The root is "grown" (shifted from right) most significant bit first, based on the pair of input bits being considered. The temp variable holds a function of the previous root (2*(2*root) + 1) and this is compared to the working register. If it is less, than the last bit of root is cleared and 2 more bits of the input are considered. If not, the bit is left as a 1, and temp is subtracted from the working register before considering the next 2 bits of the input.