# Optimizing Math-Intensive Applications with Fixed-Point Arithmetic

### CORDIC

The single biggest gain was achieved by optimizing the trigonometric and exponential functions. For the trig functions, the CORDIC method was used. (For more information on CORDIC, which is short for "COordinate Rotation DIgital Computer," see "Implementing CORDIC Algorithms," by Pitt Jarvis; www.ddj.com/architect/184408428.) CORDIC gets its name because it uses properties of rotations on a plane to calculate sines and cosines. A vector can be rotated counterclockwise by an angle q using a rotation matrix.

Equivalently, if you have two angles and such that =+, then we can first rotate by , and then by , to achieve the same effect.

The rotation by can then itself be split into further rotations by smaller and smaller angles. The benefit here comes from the fact that you can then pick a set of angles i in advance, and precompute the appropriate sines and cosines. Rather than a time-consuming and potentially inaccurate power-series calculation, the desired sines and cosines can instead be calculated by a short series of multiplications and additions. Rather than using both sines and cosines of the angles i, the cosines can be factored out:

As written, this is fine for some fixed angle theta, but what about a general angle? It can be shown that provided that:

i < i-1

and

i >= 0.5•i-1

then any angle can be made by adding or subtracting each i exactly once up to a precision determined by the number of angles n. Since cos(x)=cos(-x) and tan(x)=-tan(-x), the factored-out product of cosines can be stored as a constant multiplier once the angles have been determined, and the appropriate signs used for the tangents depending on the actual angle .

As a final simplifying step, if you choose the angles i such that tan(i)=2-j for some integer j, then this greatly simplifies the multiplication, as it is now just a simple shift.

We only need to handle angles in the range -/2 to /2, since the sines and cosines of larger angles only vary in sign (if at all), and restricting it to this range limits the number of iterations required.

The sine and cosine of an angle can thus be calculated simply by rotating the unit vector from the x axis by the required angle as described: The cosine and sine are the x and y coordinates of the rotated vector.

### Calculating arctan

The inverse tangent can easily be calculated with the CORDIC rotation tables. This time, rather than rotating the unit vector, a vector with an x component of 1 and a y component of the value for which we want the arctan is rotated until it has a y value of 0.

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>