CORDIC (COordinate Rotation DIgital Calculation) finds the sine or cosine of an angle iteratively, using only simple math operations such as add, subtract, compare, shift, and table lookup.

Other pages on CORDIC

Implementing Sine on the PIC: http://www.brouhaha.com/~eric/pic/sine.html

CORDIC tutorial by Ingo Cyliax: http://www.ezcomm.com/~cyliax/Articles/RobNav/sidebar.html

CORDIC bibliography: http://www.taygeta.com/cordic_refs.html

HTML notes

The last word in this sentence should appear in superscript.
The last word in this sentence should appear in subscript.
This line should end with the degree symbol �
I belive � is actually a Danish vowel, but it's the closest I can get to 'theta' or 'phi' in the Latin character set.

Vector rotation


The diagonal blue line is angle �1 above the horizontal. The diagonal red line is the blue line rotated counter-clockwise by angle �. The new X and Y values are related to the old X and Y values as follows: 
X2 = X1 * cos(�) - Y1 * sin(�)
Y2 = X1 * sin(�) + Y1 * cos(�)

Iterative rotation

For CORDIC, the final angle �2 is the angle of interest; the angle whose sine or cosine we want to calculate. The initial angle �1 is set to a convenient value such as 0. Rather than rotating from �1 to �2 in one fell swoop, we move in steps. With careful choice of step values, the only math used is shifts and adds.

The equations above can be re-written as: 

X2 = cos(�) * [ X1 - Y1 * tan(�) ]
Y2 = cos(�) * [ X1 * tan(�) + Y1 ]
Values for � are chosen such that tan(�) is a fractional power of 2: 
tan(�21) = 1/1		�21 = 45�		cos(�21) = 0.707107
tan(�32) = 1/2		�32 = 26.5650�		cos(�32) = 0.894427
tan(�43) = 1/4		�43 = 14.0362�		cos(�43) = 0.970142
tan(�54) = 1/8		�54 =  7.12502�		cos(�54) = 0.992278
tan(�65) = 1/16		�65 =  3.57633�		cos(�65) = 0.998053
tan(�76) = 1/32		�76 =  1.78991�		cos(�76) = 0.999512
tan(�87) = 1/64		�87 =  0.895174�	cos(�87) = 0.999878
tan(�98) = 1/128	�98 =  0.447614�	cos(�98) = 0.999969
This lets us replace the multiplication by tan(�) with a simple, fast right-shift operation. But what about the cos(�) factors?

First iteration (from X1, Y1 to X2, Y2): rotate by angle �21 

X2 = cos(�21) * [ X1 - Y1 * tan(�21) ]
Y2 = cos(�21) * [ X1 * tan(�21) + Y1 ]
Second iteration (from X2, Y2 to X3, Y3): rotate by angle �32 
X3 = cos(�32) * { X2 - Y2 * tan(�32) }
Y3 = cos(�32) * { X2 * tan(�32) + Y2 }
Plug in the values of X2 and Y2 from the first iteration: 
X3 = cos(�32) * { cos(�21) * [ X1 - Y1 * tan(�21) ] - cos(�21) * [ X1 * tan(�21) + Y1 ] * tan(�32) }
   = cos(�32) * cos(�21) * { [ X1 - Y1 * tan(�21) ] - [ X1 * tan(�21) + Y1 ] * tan(�32) }
The cosine factors fall out, to form an iterative product, i.e. 
cos(�21) * cos(�32) * cos(�43) ... * cos(�nn)
Expressing the � values in terms of inverse tangents gives the equivalent product series

The value to which it converges, 0.607253, is the aggregate constant. We can ignore the cos(�) terms and simply multiply by the aggregate constant before or after the iteration.

Example

C source code for this example: cordic.c

Find the sine of 28.027� 

� = 0�
cos(�) = 1	X = 1
sin(�) = 0	Y = 0
Rotate from 0� to 45� (�21 = 45�) 
X' = X - Y / 1		= 1 - 0 / 1			= 1
Y' = X / 1 + Y		= 1 / 1 + 0			= 1
Rotate from 45� to 18.435� (�32 = -26.565�). Because this is a negative angle, and because the tangent function is odd, we change the sign of the numbers that get shifted: 
X' = X + Y / 2		= 1 + 1 / 2			= 1.5
Y' = -X / 2 + Y		= -1 / 2 + 1			= 0.5
The aggregate constant is not affected because it is a product of cosines, and the cosine function is even.

Rotate from 18.435� to 32.471� (�43 = 14.036�) 

X' = X - Y / 4		= 1.5 - 0.5 / 4			= 1.375
Y' = X / 4 + Y		= 1.5 / 4 + 0.5			= 0.875
Rotate from 32.471� to 25.346� (�54 = -7.125�) 
X' = X + Y / 8		= 1.375 + 0.875 / 8		= 1.484375
Y' = -X / 8 + Y		= -1.375 / 8 + 0.875		= 0.703125
Rotate from 25.346� to 28.922� (�65 = 3.576�) 
X' = X - Y / 16		= 1.484375 - 0.703125 / 16	= 1.440429
Y' = X / 16 + Y		= 1.484375 / 16 + 0.703125	= 0.795898
Rotate from 28.922� to 27.132� (�76 = -1.790�) 
X' = X + Y / 32		= 1.440429 + 0.795898 / 32	= 1.465300
Y' = -X / 32 + Y	= -1.440429 / 32 + 0.795898	= 0.750884
Rotate from 27.132� to 28.027� (�87 = 0.895�) 
X' = X - Y / 64		= 1.465300 - 0.750884 / 64	= 1.453567
Y' = X / 64 + Y		= 1.465300 / 64 + 0.750884	= 0.773779
Almost done; just have to multiply by the aggregate constant: 
sin(28.027�) = 0.607253 * Y = 0.46988
cos(28.027�) = 0.607253 * X = 0.88268
To avoid these multiplies, the initial value of X can be set to 0.607253 instead of 1. Doing this means rotating a vector of length 0.607253 (instead of length 1) back and forth between the X and Y axes.

At each iteration above, a decision is made whether to add or subtract the next value of �. This is made by comparing � with the target angle. To implement this in software, a table of � values is needed, similar to the one above.