Re: square root???
can u explain Salam2000 method......hard to understand???
Synchronous Square Root Computing Machine
________________________________________
Background
Computing square root of a real number is a fundamental mathematical operation. Before the invention of calculator and computer, people would use method such as bisection and Newtonian algorithm to manually calculate square root. Today, a few buttons pushed, we get the result in no time. In this project we will implement a synchronous square root machine using a simple algorithm.
Square Root Algorithm
1. Split the given number into groups, each containing two digits, starting from the least significant bit. (In our example, these groups will be "89", "34", and "3".)
2. Find the largest number, which when multiplied by itself does not exceed the number, created by the first two-digit group. Write down this number as the first digit of the result. (In our case, the first two-digit number is "3" and the number, which when multiplied by itself does not exceed "3", is "1".)
3. Subtract the square of this number from the number given by the first two digits and concatenate this number with the next two digits from the initial number. (In our case, we have to subtract "1 x 1 = 1" from "3" and then concatenate it with "34". As a result, we get 234.)
4. Multiply by two (for binary numbers, it will be just a shift!) the number, which constitutes the result computed so far, and concatenate it with the largest digit, which satisfies the following condition: the product of this digit and the number resulting from concatenation does not exceed the number received at the previous step. (In our case, the result computed so far is "1"; multiplied by two it will be "2", and the digit to be selected is "8" because "28 x 8 = 224 < 234", while "29 x 9 = 261 > 234".)
5. Write down the digit, which we have just found (in our case, "8") as the next digit of the result.
6. Subtract 224 from 234 and concatenate it with the next group of numbers. In our case it is "1089".
7. If the resulting number (in our case it is "1089") is equal to 0 (the square root is extracted exactly), stop. Else go to step 4.
If the square root cannot be extracted exactly, algorithm should be stopped at step 7 when we have found enough digits belonging to the floating-point part of the result.
To implement this machine we will need shift registers, a subtractor, a comparator, and a few registers to hold intermediate values. Of course, we will also need a FSM to controller the flow of the data.