From: cameron@symcom.math.uiuc.edu (Cameron Smith)
Subject: Re: LOGS AND CALCULATORS
Organization: none
Date: Thu, 1 Oct 1992 16:53:08 GMT

In article <4328.2ACA0959@puddle.fidonet.org>,
Jon.Church@f455.n109.z1.fidonet.org (Jon Church) asks
several questions about computing transcendental functions.

> How do you calculate the natural log by hand?

The best simple way that I know of uses a combination of two series.
Since the derivation of it is a bit involved, I'm going to post it
as a separate message following this one.

> Or the log to base 10 if that is easier.

No, the easiest way (by hand or by machine) to calculate a "common"
(base 10) logarithm is to calculate the "natural" log (base e) and
divide by the natural log of 10 (which is roughly 2.302585092994045684).
This makes use of the identity that

    log c
       a
   -------  =  log c
    log b         b
       a

The reason that it's done this way is that there are approximations for
natural logs that are easy to compute (like the one I'm going to post),
and the extra step of division (or, more realistically, multiplication
by the inverse, since multiplication is a little easier to perform than
division) isn't very costly.  (The reciprocal of the natural log of 10
is about 0.434294481903251827651128918916605082294397.)  Using a series
(or other method) that computed base-10 logs "directly" would involve
many nasty numbers instead of just this one.

A calculator that has a "log-10" button probably stores the above
constant rather than recomputing it each time.  But to compute the
logarithm of an arbitrary number "x" to an arbitrary base "a" you'd
compute the natural logs of x and a and then divide.

> Would this be the method that a calculator would use?

No, not a well-designed calculator anyway.

Consider this: the rational numbers give us better approximations
to real numbers than the integers do.  For example, all you can
say about the square root of two with integers is that it's between
1 and 2, but with rationals you can say that it's between 14/10
and 15/10, or between 141/100 and 142/100, or that it's between
1414/1000 and 1415/1000, or....  In short, you can "pin down" the
value of the square root of two to any desired degree of accuracy
by using rational numbers, which is much better than you can do
with integers.

Just as we can build the rational numbers from the integers, we can
build the rational *functions* from the polynomials: a rational
function is the ratio of two polynomials.  The polynomials are a
subset of the rational functions just as the integers are a subset
of the rationals: the integer 2 is the rational number that has the
integer 2 as numerator and the integer 1 as denominator, and a polynomial
can be regarded as a rational function that has that polynomial as
numerator and the constant polynomial 1 as denominator.

The important point in all this is that just as we can get better
approximations to real numbers with ratios of integers than we can
with the integers alone, similarly we can get much better approximations
to real-valued functions with ratios of polynomials than we can with
polynomials alone.  Using series to approximate a function basically
means using a polynomial (since, in order to do a specific numerical
computation, we must truncate the series after some point, turning it
into a polynomial).  By using the ratio of two polynomials instead of
a single polynomial we can get much better results with not much more
computation, and this is how well-designed calculator and computer
algorithms usually work.

Techniques for constructing rational-function approximations to real
functions usually start with one or more series and then do algebraic
manipulations on those in order to come up with the coefficients for
the numerator and denominator polynomials of the rational approximant.
One such method is that of Pad'e (that's supposed to be spelled
P - A - D - E-with-acute-accent); I imagine you would find it in any
modern book on numerical analysis.  Unfortunately such techniques are
cumbersome to perform by hand, which is one reason I'm going to post
a series method instead.  For more details, see the answer to the next
question. 

> How do calculators figure trig functions?
> Do they use series approximations?

More likely they use rational function approximations, several for
each function.  A lookup in a small table decides which approximation
function to use, then that function is evaluated (compute two polynomials
and divide their values).  To see why it's done that way, read on.

First of all, note that if you can compute the sine and cosine
of angles in the interval 0 to 45 degrees (equivalently, 0 to Pi/4
radians) then you can compute all sines and cosines, by using
identities based on reflection and complementary and supplementary
angles.  Such identities include:

   cos(-x) = cos(x)
   sin(-x) = - sin(x)
   cos( Pi/2 - x ) = sin(x)
   cos( Pi - x ) = - cos(x)
   sin( Pi - x ) = sin(x)

So it's sufficient to be able to calculate sines and cosines for the
interval 0 to Pi/4 radians.

Now, at different points within that interval, different rational
approximating functions for the same trig function will give
different degrees of accuracy (say, number of correct decimal
digits) for the same amount of computational effort (number of
additions and multiplications).  In general, the larger the interval
over which a given degree of accuracy is desired, the more complicated
a single function must be to cover that interval.  To get acceptable
accuracy over the whole interval 0 to Pi/4 with a single approximating
function, the function would have to have many, many terms in its
numerator and denominator.  But if you divide the interval into
pieces and build a separate approximating function for each piece,
then the separate functions don't have to be nearly as complicated
as the one function that tries to cover the whole interval at once
would have to be.

Therefore a smart calculator (or computer) algorithm will usually
break up the interval 0 to Pi/4 into three or four subintervals,
and have a table listing a good rational function approximation for
each of sine and cosine for each subinterval.  When asked to compute
the sine or cosine of an angle (in radians), the algorithm first uses
identities like the ones above to reduce the angle into the interval
0 to Pi/4, then looks up in the table to see which subinterval the reduced
angle falls into, then uses the appropriate approximating function for
that subinterval.  Not much additional memory, if any, is required to
store coefficients for 8 reasonably simple approximating functions
instead of a single complicated one, and the comparisons necessary
to check which subinterval the reduced angle falls into take far less
time than would be required in computing extra terms of any one
approximating function in order to get good accuracy over the whole
interval.

Tangents and other trig functions (including arctangents) are handled
similarly (a table of functions for each function/co-function pair).
It is NOT a good idea to compute tangents by dividing sines by cosines.
For one thing, it's better to evaluate a single function in order to
approximate a tangent directly than it is to compute both sine and cosine
and then divide; also, division by small numbers (as cosines near Pi/2
tend to be) is (for obvious reasons) numerically unstable.

> Thanks
> Jon Church

You're welcome.  For more information, look up books on "numerical
analysis" in the library.  It's a fascinating subject.  We are used
to thinking of arithmetic operations as "exact", but in fact on any
real machine with finite storage we can't represent most real numbers
exactly anyway (because irrational numbers have infinite expansions),
and the algorithm error combined with the representation error makes
"fuzzy" arithmetic with "fuzzy" numbers a very different thing from
what we're used to in high school algebra.

--Cameron Smith
  cameron@symcom.math.uiuc.edu