Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!cs.utexas.edu!uunet!iscuva!jimc
From: jimc@iscuva.ISCS.COM (Jim Cathey)
Newsgroups: comp.sys.mac.programmer
Subject: Re: How to Cosine
Message-ID: <2650@iscuva.ISCS.COM>
Date: 30 Oct 89 22:43:22 GMT
References: <2157@hudson.acc.virginia.edu> <2143@draken.nada.kth.se> <23401@cup.portal.com> <28548@iuvax.cs.indiana.edu>
Organization: ISC Systems Corporation, Spokane WA
Lines: 62

In article <28548@iuvax.cs.indiana.edu> viking@silver.bacs.indiana.edu (Jon W. Backstrom) writes:
>In article <23401@cup.portal.com> wetter@cup.portal.com (Pierce Wetter) writes:
>>   You want to use something called a CORDIC algorithm. If I remember 
>>correctly it uses shifts to do the divisions and multiplications by powers
>>of two, and uses some algoritm that only requires divison and multiplication
>>by powers of two. CORDIC is the name of the machine the algorithm was 
>>implemented for.

>Where is Jim Cathey when you really need him?!  :-)   Jim converted a
>fractal landscape program, originally published in Creative Computing,
>to use cordic rotators and the speedup is indeed amazing.  The actual
>work involves multiplication by powers of two and this required only
>shifting bits in the code.

I be here!  Though I am a staunch supporter of CORDIC, I don't think it
is what the originator of this thread needs to solve his cosine
problem.  Raw CORDIC (Coordinate Rotating DIgital Computer or somesuch)
is very good at rotating points around an axis as it never needs to
compute trig values at all.  It's capable of rotating an integer point
atan(1/2^integer_shiftcount) [I think] per step -- multiple steps at
differing shift counts can get you to more exact rotations.  I used
CORDIC in the fractals program to rotate an essentially 3D set of
integer data points about the Z and X axes prior to plotting it to the
screen.  The exact amount of shifting was immaterial to me so long as
the result looked good.  

For those who care, counter-clockwise CORDIC is:

	y' = y + (x >> shiftcount)
	x' = x - (y' >> shiftcount)

which is 6 instructions (per step) on the 68000.  Note well the use of y'
and not y in the second equation -- use of y will result in a rotator
that spins out into the walls instead of whirling quietly in place.  Best
results are obtained when you're using a fixed-point data type that is
normalized so that the magnitudes are large when considered as a signed
integer (so that the delta terms don't degenerate to zero).  CORDIC will
wobble a little bit as it spins, so don't normalize to +/- 32767, +/- 32000
will give a little breathing room.  (Same argument for long integers.)

There was an article in BYTE in '77 or '78 about using CORDIC for trig
functions, but it looked overly complicated compared to raw CORDIC.  Someone
also posted to the net some CORDIC trig functions, but I've never looked
at them (squirrel instinct made me grab them).

I believe HP used CORDIC for the trig functions in the HP-35 calculator,
but all later models use Chebyshev (sp?) polynomials because they are faster
and more accurate.

I think the best results for medium-precision cosine might be a combination
of table lookup, fast inline integer math, and (most importantly) good
range reduction so that the table isn't too big.  I'm pretty sure you only
need a 0-45 degree table, the rest can be deduced from trig reductions.

+----------------+
! II      CCCCCC !  Jim Cathey
! II  SSSSCC     !  ISC-Bunker Ramo
! II      CC     !  TAF-C8;  Spokane, WA  99220
! IISSSS  CC     !  UUCP: uunet!iscuva!jimc (jimc@iscuva.iscs.com)
! II      CCCCCC !  (509) 927-5757
+----------------+
			"With excitement like this, who is needing enemas?"