[erlang-questions] How to calculate series expansion e^x

[Richard A. O'Keefe]

On 25/02/2015, at 11:00 am, Harit Himanshu <harit.subscriptions@REDACTED> wrote:

> I am trying to learn Functional Programming and Erlang by practicing problems available online. 
> 
> One question where I don't know about solving it is  
> 
> The series expansion of ex is given by:
> 
> 1 + x + x2/2! + x3/3! + x4/4! + .......
> 
> Evaluate e^x for given values of x, by using the above expansion for the first 10 terms.
> 
> 
> The problem statement could be found here
> 
> Can someone guide me how this could be achieved in Erlang?

The first 10 terms of exp(X) are
     X    X^2   X^3         X^9
1 + --- + --- + --- + ... + ---
     1     2     6           9!
This is a polynomial.  We can evaluate it cheaply using
Horner's Rule.  Any time you have a polynomial to
evaluate, you should think about using Horner's Rule.

     X     /     X    /      X        /      X  \   \ \
1 + --- * | 1 + --- * | 1 + --- * ... | 1 + --- | ...| |
     1     \     2    \      3        \       9 /   / /

We can see a building block here: 1 + (X/n)*Rest.

So let's make a function for the building block:

step(X, N, Rest)
  when is_float(X), is_float(N), is_float(Rest) ->
    1.0 + (X/N)*Rest.

There are 9 steps, which is small enough to do by hand:
(NINE steps to get TEN terms.  I hope that's clear.)

exp(X)
  when is_float(X) ->
    step(X, 1.0, step(X, 2.0, step(X, 3.0,
    step(X, 4.0, step(X, 5.0, step(X, 6.0,
    step(X, 7.0, step(X, 8.0, step(X, 9.0, 1.0))))))))).


I should point out that this is a lousy way to compute
exp(X) for abs(X) "large".  Waving hands vaguely, you
want X^10/10! "small".  The relative error for X = 1.0
is -1.1e-7, for X = 2.0 is -4.6e-5, and for X = 4.0 is
a scary -0.0081.

One technique that's used in cases like this is
RANGE REDUCTION.  e^x = 2^(1.442695... * x).
To begin, scale x by log of e to the base 2,
and separate that into an integer part N and a fraction
part F.  e^x is then 2^(N+F) = 2^N*2^F.  Since F is
"small", we can use something like this polynomial.
And then we can use the equivalent of C's ldexp() to
handle the 2^N* part.  Or we could if Erlang _had_ an
equivalent of ldexp().

You don't really need the is_float/1 tests; I put them in
so that the compiler could generate better native code.