ken (04/20/83)
The CORDIC algorithms are superb for implementing trigonometric,
inverse trigonometric, and hyperbolic functions using integer
arithmetic. I have two such functions implemented in C for the PDP-11
computer: One is called polarize() and the other rotate().
Polarize() converts from rectangular to polar coordinates. It is given
rectangular coordinates (x, y) and returns polar coordinates (r, theta).
Polarize() is more of an arctan2(x, y) than an arctan(z), but gives
an angle around the whole circle, rather than just the right-half
plane.
Rotate() rotates a rectangular vector by a specified angle, but can be
used to convert from polar to rectangular coordinates. It is given
rectangular coordinates and an angle, and it returns rectangular
coordinates.
You get your choice of degrees, radians, or brads, or whatever other
angle measure you want. The difference is in the arctangent table.
The scheme is as follows: Rotate a vector through successively smaller
angles until it meets a certain condition. For polarize(), it is until
the Y-coordinate is zero. For rotate(), it is until the rotation angle
is zero. The papers prove convergence. Approximately one bit of
accuracy is got for each iteration through the loop. Implementation on
a 29116 shows that either of the two algorithms takes six times as long
as a multiplication. The basic CORDIC algorithm elongates vectors by a
factor of approximately 3.7, so if the true vector length is desired,
the CORDIC pseudo-rotations must be followed by a couple of multiplies,
raising the cost to 8 multiplications.
These algorithms or simple pertubations thereof may be used for polar-
to-rectangular conversion, rectangular-to-polar conversion, rotation of
a vector, forward and inverse trigonometric and hyperbolic functions,
exponential, and logarithms. Chen's paper touches on using CORDIC
iterations for generation of arbitrary functions (but is difficult to
read), and Walther's paper is probably the best all-around reference.
References:
Chen, T. C.
"Automatic Computation of Exponentials, Logarithms, Ratios, and Square Roots",
IBM J. Res. Develop., July 1972, pp. 380-388
Despain, A. M.
"Fourier Transform Computers Using CORDIC Iterations",
IEEE Trans. Comp., vol. C-23, no. 10, Oct. 1974, pp. 993-1001
Turkowski, K. E.
"Anti-Aliasing through the Use of Coordinate Transformations",
ACM Transactions on Graphics,
Vol. 1, No. 3, July 1982, pp. 215-234
Volder, J. E.
"The CORDIC Trigonometric Computing Technique",
IRE Transactions on Electronic Computers,
vol. EC-8, no. 3, Sept. 1959, pp. 330-334
Walther, J. S.
"A Unified Algorithm for Elementary Functions",
Proc. AFIPS 1971 Spring Joint Computer Conference,
pp. 379-385
Any interested parties may send me mail, and I will ship a copy of both
polarize.c and rotate.c. If enough interested parties ask, I will post
it in net.sources.
Ken Turkowski
{decvax,ucbvax}!decwrl!turtlevax!ken