## 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.

**Algorithm**

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 = 2^{n/2 - 1}, 2^{n/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:

**Try #1**

^{n/2 - 1}, root = 0

^{2}<= N)

^{2}. We can calculate that at the end of each step and hold onto it for the next step. In our first try above, we were checking ((root + Delta)

^{2}<= N). Expanding that out, it is equivalent to checking the condition (root

^{2}+ 2*root*Delta + Delta

^{2}<= N), which we can reorganize as (2*root*Delta + Delta

^{2}<= N - root

^{2}), finally substituting in M to get (Delta *(2*root + Delta) <= M). There are now two multiplies necessary to compute our condition. Fortunately, one is a multiply by 2, the other is a multiply by a power of 2, so all we really have is shifts, which we can do just fine in the UDBs. This gives us a much more efficient algorithm:

**Try #2**

^{n}

^{/2 - 1}, root = 0, M = N

**Try #3**

^{n-2}, q = 0, M = N

^{0}to 2

^{-1}. Therefore, q (which we are using to track 2*Delta*root) is now equal to 2*(2

^{-1})*root, our final answer.

ALL CONTENT AND MATERIALS ON THIS SITE ARE PROVIDED "AS IS". CYPRESS SEMICONDUCTOR AND ITS RESPECTIVE SUPPLIERS MAKE NO REPRESENTATIONS ABOUT THE SUITABILITY OF THESE MATERIALS FOR ANY PURPOSE AND DISCLAIM ALL WARRANTIES AND CONDITIONS WITH REGARD TO THESE MATERIALS, INCLUDING BUT NOT LIMITED TO, ALL IMPLIED WARRANTIES AND CONDITIONS OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT OF ANY THIRD PARTY INTELLECTUAL PROPERTY RIGHT. NO LICENSE, EITHER EXPRESS OR IMPLIED, BY ESTOPPEL OR OTHERWISE, IS GRANTED BY CYPRESS SEMICONDUCTOR. USE OF THE INFORMATION ON THIS SITE MAY REQUIRE A LICENSE FROM A THIRD PARTY, OR A LICENSE FROM CYPRESS SEMICONDUCTOR.

Content on this site may contain or be subject to specific guidelines or limitations on use. All postings and use of the content on this site are subject to the Terms and Conditions of the site; third parties using this content agree to abide by any limitations or guidelines and to comply with the Terms and Conditions of this site. Cypress Semiconductor and its suppliers reserve the right to make corrections, deletions, modifications, enhancements, improvements and other changes to the content and materials, its products, programs and services at any time or to move or discontinue any content, products, programs, or services without notice.