Implementing Complex Math using the Datapath | Cypress Semiconductor
Implementing Complex Math using the Datapath
If you've used the datapaths to perform operations, you know that they can perform an add or subtract and they can perform various logical operators such as AND, OR, and XOR along with shifting. A couple of the Cypress component development engineers have decided to take the capabilities of the datapaths much further. In a recent post to the Community Components section of the Cypress Forums, Richard Mc Sweeney has provided a component that can perform trigonometric functions using the CORDIC algorithm. Another component developer, CJ Cullen, has provided me with his implementation of a square root function using datapaths. I'll use the next several blog posts to go through CJ's description of the implementation he put together.
The approach we'll use for a square root algorithm is essentially a guess-and-check. To calculate the square root of N, we will continue to make a guess (let's call it root) until that guess is as close to sqrt(N) as possible without going over. At each guess, we will be checking if (root + Delta)2 <= N, where Delta gets progressively smaller until it is beyond the precision of our data type. If (root + Delta)2 is smaller than N, we will add Delta to root to get closer to our final answer. To do this intelligently (and efficiently on hardware), we will use powers of 2: Delta = 2n/2 - 1, 2n/2 - 2,.., 2, 1, where n is the maximum number of bits in any N we want our algorithm to handle. For you computer-sciency types, we are essentially performing a binary search of the solution space of our problem. This gives us a first cut of our algorithm: