Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

C/C++

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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips 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.