Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Fixed-Point Math CORDIC Shift and Add for Exponentials Square Roots

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.

Previous Page | 1 Fixed-Point Math | 2 CORDIC | 3 Shift and Add for Exponentials | 4 Square Roots Next Page

RELATED ARTICLES Logging In C++ : Part 2 recls 100% .NET QuickThread: A New C++ Multicore Library C Snippet #8 CUDA, Supercomputing for the Masses: Part 14		TOP 5 ARTICLES No Top Articles.