gfs@abvax.UUCP (Greg F. Shay) (05/25/88)
Ok, I'm interested. In reply to my sin(x) in integer posting, a couple people mentioned the CORDIC algorithm which apparently performs the whole coordinate system transform without any multiplies (albeit using a small lookup table.) My application for the integer (actually fixed point) sin(x) is indeed a vector display program, which I now have converted completely to 68000 assembler (no c routines left) in the display pipeline (vector multiply, vector draw,screen clear). The bottleneck in performance is the vector by matrix multiply (six multiplies and six additions per vector). The CORDIC algorithm sounds like it will greatly speed up my display pipeline by transforming the display vectors without the vector by matrix multiply per vector. Could someone either thumbnail sketch the CORDIC algorithm for me or give a reference? Many Thanks. Greg Shay pyramid | decvax |..!abvax!gfs mandrill |
paul@torch.co.uk (Paul Andrews) (05/31/88)
In article <354@abvax.UUCP> gfs@abvax.UUCP (Greg F. Shay) writes: >Ok, I'm interested. In reply to my sin(x) in integer posting, a couple > Could someone either thumbnail sketch the CORDIC algorithm for me >or give a reference? Many Thanks. > > Greg Shay >... I looked through my references and discovered that they were fairly useless. Instead, here's some source that does ONE of the CORDIC transformations i.e. the original one, the coordinate rotation. Note that the same method generalises to do the following transformations also: sin, cos, tan, atan, sinh, cosh, tanh, atanh, exp, ln, root. The author of the best paper I know on this is J.S.Walther, unfortunately I can't give you the reference. I would've mailed this but we've yet to sort our mail out... - Paul. -------- Cut here --------- /* -------Forward declarations-----------------------*/ /* -------Constants and macros-----------------------*/ #define KR 107922 /* constant */ /* -------Exported variables/functions---------------*/ /* -------Imported variables/functions---------------*/ /* -------Static variables---------------------------*/ static int arctan [] = /* Table of atans in degrees << 16 */ { 2949120, 1740967, 919879, 466945, 234378, 117303, 58666, 29335, 14668, 7334, 3667, 1833, 918, 458, 229, 115 }; /* ************* * * * CORDIC * * * ************* ------------------------------------------------------------------------------- | Perform a cordic transformation on the arguments | | The value returned is b*cos(theta) + a*sin(theta). | | theta is an angle in the range 0 - 90 degrees. | ------------------------------------------------------------------------------- */ Cordic(a, b, theta) register int a, b, theta; { register int olda, i; a <<= 8; b <<= 8; theta <<= 16; for (i = 0; i < 16; i++) /* do this to 16 bits */ { olda = a >> i; if (theta < 0) { a += (b >> i); b -= olda; theta += arctan [i]; } else { a -= (b >> i); b += olda; theta -= arctan [i]; } } /* The value returned is b*cos(theta) + a*sin(theta) */ /* a*sin(theta) if initial b was 0 */ /* b*cos(theta) if initial a was 0 */ return ((b << 8) / KR); /* We are throwing a away, though it contains : */ /* a*cos(theta) - b*sin(theta) */ }