Path: utzoo!mnetor!uunet!husc6!mit-eddie!uw-beaver!tektronix!orca!brucec
From: brucec@orca.TEK.COM (Bruce Cohen)
Newsgroups: comp.graphics
Subject: CORDICS: Is Ken Turkowski there? (was: Fractals...Jim Cathey where are you?)
Message-ID: <2479@orca.TEK.COM>
Date: 11 Feb 88 01:45:11 GMT
References: <6019@iuvax.UUCP>
Reply-To: brucec@orca.UUCP (Bruce Cohen)
Organization: Tektronix, Inc., Wilsonville, OR
Lines: 46
Keywords: fractals, CORDIC
Summary: Where to find out about CORDICS

In article <6019@iuvax.UUCP> viking@iuvax writes:
>
>The major enhancements that Jim added to the program were to recode it in
>C and to use "a CORDIC rotator instead of trig functions".  I want to talk
>with Jim about his program....where is he?!
>
>Alternately, does anyone know anything about "CORDIC rotators"?  I'd like to
>see the source to his modification of Michiel's program.  The algorithm used
>was based on one developed by LucasFilm Ltd. and published in the Sept. '84
>Scientific American.

CORDIC (stands for COordinate Rotation DIgital Computer) algorithms are a
class of algorithms for computing approximations to transcendental
functions quickly.  They typically converge towards the solution at a rate
of one bit of precision per iteration of the loop.  The trig functions,
and maybe some of the other transcendentals, on HP calculators are
implemented with CORDICS, for instance.  The technique has been around
since at least the '50s (1959 was the earliest citation I found in about
two minutes of search, it was claimed to be the original paper), so I
doubt that that part of the algorithm is what LucasFilm claims as theirs.

The basis of the algorithm is a fast loop which rotates a vector using
only shifts and adds.  There's a nice description of how it works in an
article by Ken Turkowski in the July, 1982 issue of ACM Transctions on
Graphics.  He even shows the kernel of the algorithm in C.

I don't have time right now to write a dissertation on the algorithm.  If
you have access to Ken's article, read it.  If Ken is out there listening
as he used to be, he might be willing to write something up now, or let me
paraphrase some of his article in a day or two, when I have time.

Umm ... now that I think about it, someone (possibly Ken) sent out C sources
for a set of CORDIC functions a couple of years ago.  Anyone have those
squirreled away?

---------------------------------------------------------------------------
	"The authorities are excellent at amassing facts, though they do not
     always use them to advantage."
					Sherlock Holmes, "The Naval Treaty"

My opinions are my own; no-one else seems to want them.

Bruce Cohen
bang-syntax: {the real world}...!tektronix!ruby!brucec
at-syntax:   brucec@ruby.TEK.COM
overland:    Tektronix Inc., M/S 61-028, P.O. Box 1000, Wilsonville, OR  97070