TOPIC: Transcendental function algorithms PRODUCT: Most TI calculators ---- end abstract ------- begin documentation --- TOPIC: Transcendental function algorithms PRODUCT: Most TI calculators Past threads on Graph-TI asked about the internal methods used to compute trigonometric and other transcendental functions. We wanted to add some specific information to this dialog so that someone could perhaps develop a short module for the classroom if they would like. This topic should be interesting for background on calculators or as a good example of a math application. Most practical algorithms in use for transcendental functions are either polynomial approximations or the CORDIC method. TI calculators have almost always used CORDIC, the exceptions being the CC-40, TI-74 and TI-95 which used polynomial approximations. In the PC world, the popular Intel math coprocessors like the 8087 use CORDIC methods, while the Cyrix 83D87 uses polynomial methods. There are pros and cons to both methods. References 1 and 2 give some information on these devices but not down to the detailed algorithm level. The polynomial approximations, however, are not usually familiar ones like a Taylor's series, but more related to Chebyshev polynomials. Early work on this topic was done by Hastings (ref 3) which is a fascinating book that represents a lot of tedious work in an age when "computers" were still likely to be people! A more recent standard reference for constructing these polynomials is Hart (ref 4). A thorough treatment of the minor details one has to deal with in implementing the full algorithms for elementary functions (like binary versus decimal number representations and ranging for general arguments) is in Cody (ref 5). The CORDIC algorithm is a super example of an approach that is quite different from traditional math and which is very efficient. One often sees a very specialized problem solution like this in many areas of engineering and science, which makes exposure to ideas of this type valuable in education, at least for advanced students. CORDIC is an acronym for COrdinate Rotation DIgital Computer and was developed by J.E. Volder in 1959 (ref 6). Additional articles and one book chapter covering the technique are given in references 7 - 10. All these articles are complete enough to give the essentials of the method but each one reveals interesting variations. To give you a flavor for the idea and some material to work with without tracking down these references, we will give a worked example and a general description of the principle. The concept of CORDIC is to take an angle theta and "rotate" a vector over this angle towards zero in a series of steps such that the sum of all the steps taken equals theta and we can accumulate corresponding X and Y increments for each step such that when we complete the process, Y/X = tan(theta). Variations of this basic concept can result in all the forward and inverse trigs as well as square root, hyperbolic trigs, and the exponential and logarithm functions. Let's go through this tangent example and then summarize why it works. To make the arithmetic simple (and fast) we choose a set of angles phi(k) = atan(10^(-k)). Since the TI-85 uses 14 digit arithmetic, we would store a table like the following having 15 entries: k 0 1 2 3 4 5 ... 13 14
10^(-k) atan(10^(-k)) [13 dig] index 1 .78539816339745 .7853981633974 1 .1 .09966865249116 .0996686524912 2 .01 .00999966668667 .0099996666867 3 .001 .00099999966667 .0009999996667 4 .0001 .00009999999967 .0000999999997 5 .00001 .00001000000000 .0000100000000 6 1e-13 .00000000000010 .0000000000001 14 1e-14 .00000000000001 15
Manually enter the above values into a vector named "ctab" for the TI-85 or enter the fourteen 13 digit values into the {x} STAT list on the TI-81 (since the TI-81 uses 13 digits of precision). The index number at the right will be the position of each of these values in the list. Then, we execute the following algorithm: (Note: theta should be between 0 and pi/2 radians).
to compute Z=tan(theta) set K=0 set X=1 set Y=0 while (theta not equal to zero) while (theta less than atan(10^(-K)) ) K = K + 1 end while theta = theta - atan(10^(-K)) {this is a fixed point add} temp = X X = X - 10^(-K) * Y {the multiply is a digit shift} Y = Y + 10^(-K) * temp end while Z=Y/X
The following TI-85 program will do this: \START\ \COMMENT=Program file dated 03/08/93, 13:06 \NAME=CORDIC \FILE=cordic.85P 0\->\cnt 0\->\K 1\->\X 0\->\Y Input "Angle (rad)? ",\LC-theta\ While (\LC-theta\\\0) While (\LC-theta\\K End cnt+1\->\cnt \LC-theta\-ctab(K+1)\->\\LC-theta\ X\->\temp X-10^(\(-)\K)*Y\->\X Y+10^(\(-)\K)*temp\->\Y Disp cnt,K,Y/X End Disp Y/X \STOP\ A TI-81 program can be easily derived from this by using the {x} list for the constants. Why does this work? If we consider the input angle to define a vector from the origin whose length is fixed (ie the rotation of the vector describes a circle), the following equations describe the rotated coordinates X' and Y' as the vector rotates from an initial position defined by X,Y: X'=X cos a + Y sin a Y'=Y cos a - X sin a or X'/cos a = X + tan a * Y Y'/cos a = Y - tan a * X By breaking up the angle "a" into successively smaller parts (10^-k) and storing atan(10^-k) for each part, you can recognize the iteration from the example program. Rotate the angle by a=atan(10^-k) The new X = old X + tan(atan(10^-k)) * old Y The new Y = old Y - tan(atan(10^-k)) * old X In fixed point arithmetic, of course, the first operation is a fixed point add (subtract), the second two operations are just a digit shift (sometimes) and an add. This is why the operation is so fast. Sin and cos can come from straightforward identities: Sin a = tan a / sqrt(1 + (tan a)^2) Cos a = 1 / sqrt(1 + (tan a)^2) The many other variations are covered in the references. Some brief ideas of simple variations are: Inverse trigs: To get the inverse tangent use the same constants as the example. Set K=0; theta=0; X=1; enter with Y as the argument while (Y not equal to 0) while(Y< 10^-k * X) K = K + 1 end while theta = theta - atan(10^(-K)) {this is a fixed point add} temp = X X = X - 10^(-K) * Y {the multiply is a digit shift} Y = Y + 10^(-K) * temp end while return theta Exponential: Use constants: LN(1+10^-k) k=0,1,2... For Y = exp(X) Set K=0; Y=1; enter with X as the argument while (K < 14) {depending on number of digits} Z = LN(1+10^-k) {stored constants} while (X >= Z) X = X - Z Y = Y + 10^-k * Y {digit shift and add} end while K = K + 1 end while return Y In a real calculator algorithm, there are lots of other details to worry about. One that was mentioned by someone was ranging large angles, like sin(10^22). Since we do have to divide by pi to remove multiples of 2pi, this causes us to lose about one digit of accuracy for each decade in the argument. For this reason some calculators use a double length pi. The TI-68 is an example of this kind of calculator, and if you compare trigs on radian arguments you can see this effect: sin(100000000) = .9316390271097260... TI-85 = .93163910531978 last 8 digits wrong TI-68 = .9316390271097 all digits correct but also, sin(10*pi) = 0 exactly TI-85 = 0 TI-68 = 2.067615373566 e-12 This last result where the TI-68 gets a non zero value for sin(pi) is due to using the double length pi for ranging but a 13 digit value for pi on the keyboard since that is all that can be used for calculations. The sin of 31.4159265359 is 2.067615373566167... e-12 and this is what the TI-68 is doing. Even though this double length pi approach is more accurate, we have found many users confused by the TI-68 result for sin(n*pi). Also, from a real world problem solving point of view, large radian angles are not frequently encountered. For these reasons, most of our calculators use a single length pi for ranging. Ref 1. Palmer, John F. and Morse, Stephen P., "The 8087 Primer", Wiley Press, 1984. Ref 2. Glass, L. Brent, "Math Coprocessors", Byte Magazine, January 1990, Pg. 337-348. See discussion in box, pg 340. Ref 3. Hastings, C, Jr., "Approximations for Digital Computers", Princeton University Press, 1955. Ref 4. Hart, John F., et al, "Computer Approximations", Robert E. Krieger Publishing Co, 1978. Ref 5. Cody, William J., Jr. and Waite, William, "Software Manual for the Elementary Functions", Prentice-Hall, 1980. Ref 6. Volder, J.E., "CORDIC Trigonometric Computing Technique", IRE Transactions on Electronic Computers, EC-8, Sept. 1959, pp Ref 7. Schmid, Hermann and Bogacki, Anthony; "Use decimal CORDIC for generation of many transcendental functions", EDN magazine, February 20, 1973, pp 64-73. Ref 8. Jarvis, Pitts, "Implementing Cordic Algorithms", Dr. Dobbs Journal, October 1990, pp 152-156. Ref 9. Ball, J.A., "Trigonometry in Two Easy Black Boxes", BYTE, May 1979, pp 184-194. Ref 10. Ruckdeschel, F.R., "BASIC Scientific Subroutines Vol II", Byte/McGraw-Hill Publications, 1981. Chapter 4 is devoted to the CORDIC method. -------------------------------------------------------------------------- TI GRAPHIC PRODUCTS TEAM Texas Instruments (Consumer Products) P.O. Box 650311 M/S 3908 Internet:
[email protected] Dallas, Texas 75265 Fax: 214-917-7103 ------------------------------------------------------------------------------ end documentation ------- begin ascii ------- end ascii ------- begin uue ------- end uue ----