sci.math #141946 (3 + 1032 more) ( )--[1]
From: Vladimir BAYKOV
Newsgroups: sci.math
[1] Re: CORDIC: list of publications
Date: Thu, 13 Jun 96 09:32:48 +0400
Organization: cit_etu
Message-ID:
References: <199606130234.TAA03738@hotpage.Stanford.EDU>
X-NNTP-Posting-Host: vladusr
X-Mailer: BML [MS/DOS Beauty Mail v1.36h]
X-Mail2News-Path: gw.pu.ru!citetu.UUCP!vladusr
> MikeWells wrote:
> >I guess this is a FAQ in many ways, but how do modern calculators give
> >values of sine and cosine (and tan)? It would be very helpful if you coul
d
> >email any replies as this newsgroup is _much_ too big for me to download
> >on a cheap modem. :-)
> Texas Instruments has a web document on this:
> http://ds1.internic.net:80/pub/graph-ti/calc-apps/info/cordic.txt
> TI says they use CORDIC; the document cited above describes CORDIC
> briefly and gives some further bibliographic citations.
> Regards,
> --
> Mark Janeba (503)370-6123
More details about CORDIC you can find in
http://devil.ece.utexas.edu/cordic.html
Vladimir Baykov
vlad@vlad.usr.etu.spb.ru
End of article 141946 (of 142264) -- what next? [npq]
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 10^(-k) atan(10^(-k)) [13 dig] index
0 1 .78539816339745 .7853981633974 1
1 .1 .09966865249116 .0996686524912 2
2 .01 .00999966668667 .0099996666867 3
3 .001 .00099999966667 .0009999996667 4
4 .0001 .00009999999967 .0000999999997 5
5 .00001 .00001000000000 .0000100000000 6
...
13 1e-13 .00000000000010 .0000000000001 14
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: ti-cares@lobby.ti.com
Dallas, Texas 75265 Fax: 214-917-7103
---------------------------------------------------------------------------
---- end documentation ----
---- begin ascii ----
---- end ascii ----
---- begin uue ----
---- end uue ----