White Paper Discuss: 296's CORDIC Math Library

[CD47-Bot]

Thread created automatically to discuss a document in the White Papers.

296's CORDIC Math Library by Pat Fairbank

[Pat Fairbank]

Hello all,

We at 296 decided to share our student-developed math library with the CD community. We needed trig functions for our robot positioning system, so we wrote our own using the CORDIC algorithm. The library includes integer sine, cosine, and arctangent, all accurate to +- 1/16777216, as well as a few other useful functions.

I hope this comes in useful for those of you who need accurate trig functions.

[Astronouth7303]

A "Short Long"? Isn't this contradictive? or just an oxymoron? I thought there were short ints and long ints.

[Pat Fairbank]

Well, short ints are 16 bit, long ints are 32, and I guess that they needed a name for a 24 bit int, so they called it a short long.

[mtrawls]

We didn't use trig in our final implementation ... but in testing we did consider it, and also decided on the CORDIC algorithm. There is an added advantage of CORDIC that your library currently doesn't utilize -- it can compute both the sin and cosine at the same time (which you do, but then you throw one of them away). For our trig needs, anyway, we needed the sin and cos of the same angles.

Implementing this in a math library (admittedly more general than our custom implementation), would be interesting conceptually. Maybe create a structure called angle.

struct angle {
  short long angle;
  short long sin, cos;
  ...
};
...
short long Sin (angle ang) {
  ...
  ang.cos = blah;
  ang.sin = more blah;
  return ang.sin;
}

This function in addition to the normal sin function (i.e., that doesn't take a struct as an argument). Maybe this is too much for something that is too specific, whereas this is a general library. But then again, maybe other teams had the same need as we did, and could stand to benefit from not doing extraneous processing. Note that all this is off the top of my head without thinking about it as often as I ought to (which for some reason is why I end up with bugs in my code ... go figure). I can imagine other implementations, equally or more valid than this -- this suggestion is more conceptual than offering actual code implementation.

[Greg Ross]

Originally Posted by mtrawls

We didn't use trig in our final implementation ... but in testing we did consider it, and also decided on the CORDIC algorithm. There is an added advantage of CORDIC that your library currently doesn't utilize -- it can compute both the sin and cosine at the same time (which you do, but then you throw one of them away). For our trig needs, anyway, we needed the sin and cos of the same angles.

Implementing this in a math library (admittedly more general than our custom implementation), would be interesting conceptually. Maybe create a structure called angle....

I have not really looked into CORDIC before. It's interesting that it computes both sine and cosine at the same time. And I like your idea of making them both available. I think I would probably choose an approach where I just save both values, and then the next time a sine or cosine is called for, check to see if the angle is the same as last time. If it is, then I could just return the previous value. Granted there is something to to say for your idea of the struct, because it would be simple that way, to save the trig functions for a few commonly used angles.

Be that as it may, here's my suggestion of an implementation:

typedef enum {wantsSin, wantsCos} WhichFunc;

short long cordic(short long theAngle, WhichFunc theRequestedFunction)
{
	static char firstTime = 1;
	static short long prevAngle;
	static short long prevSin;
	static short long prevCos;

	unsigned char i;
	short long X = K, Y = 0, t = theAngle;
	short long dx, dy;

	// If this is the first time the function has been called, or if the
	// requested angle is different than the last time, then go ahead and
	// calculate the sine and cosine, otherwise we can skip the calculations,
	// and just return the value calculated last time.
		
	if (firstTime || (theAngle != prevAngle)) {
		if ((long) abs((long)theAngle) > 4194304)
			t = (short long) sgn((long) theAngle) * (8388608 - (short long) abs(theAngle));

		for (i = 0; i < 23; i++) {
			dx = sgn((long) X) * ((unsigned short long) abs((long) X) >> i);
			dy = sgn((long) Y) * ((unsigned short long) abs((long) Y) >> i);
			X -= (t > 0) ? dy : -dy;
			Y += (t > 0) ? dx : -dx;
			t -= (t > 0) ? e[i] : -e[i];
		} // for

		if (abs((long) theAngle) > 4194304) X = -X;

		firstTime = 0;
		prevAngle = theAngle;
		prevSin = Y;
		prevCos = X;
	} // if (firstTime ...

	if (theRequestedFunction == wantsSin)
		return prevSin;
	else
		return prevCos;
}

short long sin(short long theAngle)
{
	return cordic(theAngle, wantsSin);
}

short long cos(short long theAngle)
{
	return cordic(theAngle, wantsCos);
}

Note I took some liberties with team 296's code to suit my own personal preferences. You can take it or leave it:

• I unrolled the nested ::gasp:: ternary operators in the return statement to make it more readable.
• I changed the name of the "ang" parameter to theAngle, so that someone unfamiliar with the code won't have to stop and think "Ang? What's that? Anger? Angst? Angstrom? Automatic Number Generator?" (Yeah, I know it's FAIRLY obvious from the context, but I prfr rdg fl wrds nstd f abbrvs. cn u dg it?)
• I changed the name of the second parameter of the cordic() routine (again so it's more obvious what the parameter is used for) and I made it an enum so that you never have to wonder whether 0 or 1 means sine or cosine.
• I added a couple of end brace comments so it's easier to match up opening and closing braces.
• I moved the cordic() function in front of sin() and cos(), so I wouldn't need a prototype for cordic().