How to implement arctan(x) without using standard library?

Discussion in 'C++' started by Gerald, Dec 9, 2005.

  1. Gerald

    Gerald Guest

    Recently, my program need to be run in embeded enviroment, and I cann't
    use standard library. But I need to use arctan(x), so I implement it
    like the following:

    inline double pow(double x, size_t n) {
    if (n == 0)
    return 1;
    else if (n % 2 == 0)
    return pow(x * x, n >> 1);
    else
    return x * pow(x * x, n >> 1);
    }

    inline double atan_Gerald(double x) {
    register double temp1 = x >= 0 ? x : -x;
    register double temp2 = temp1 <= 1.0 ? temp1 : (temp1 - 1) / (temp1 +
    1);
    register double sum = temp2;

    for (register size_t i = 1; i != 6; ++i)
    sum += (i % 2 ? -1 : 1) * pow(temp2, (i << 1) + 1) / ((i << 1) + 1);

    if (temp1 > 1.0) sum += 0.785398;
    return x >= 0 ? sum : -sum;
    }

    But I found it doesn't work efficiently like atan in standard library,
    Would you please
    help me to optimize my code or give me another suggestion?

    Thank you!

    Regards Gerald
    Gerald, Dec 9, 2005
    #1
    1. Advertising

  2. Gerald

    Gerald Guest

    I made a mistake: the 'register' before double is useless, I forget to
    delete it.
    Gerald, Dec 9, 2005
    #2
    1. Advertising

  3. Gerald wrote:
    > Recently, my program need to be run in embeded enviroment, and I cann't
    > use standard library.


    I don't think that this is a reasonable argument for not using the
    standard library! In particular, I know that there is at least one
    standard library targeted also at embedded systems: the Dinkumware
    library is available in a version tailored to embedded systems
    (although I personally don't see any justification at all in EC++...).
    See <http://www.dinkumware.com/>. The prices are definitely in a
    range where it comes much cheaper to buy the library than provide a
    quality implementation of even a single trigonometric function.

    > But I need to use arctan(x), so I implement it
    > like the following:


    I haven't implemented these functions myself and thus I might be
    entirely wrong about how I think these functions are implemented.
    Still, my understanding is that they are implemented very different
    from how you tried to implement them. The basic approach is something
    like this:

    1. Translate the function argument(s) to a minimal basic area (this
    is almost certainly not the correct term but I don't know the
    correct term). My maths is rather rusty but I think for arctan(x)
    the basic area is the range [0, 1]: all other values can be
    derived from an appropriate argument:
    - x < 0: arctan(x) = -arctan(-x)
    - 1 < x: arctan(1/x) = pi/2 - arctan(x)
    (actually, you already do this part...)
    2. For the values in basic area you look up the subrange your value
    is located in. Each subrange is associated with an approximation
    function which is just a suitably parameterized polynomial of a
    relatively small degree which can be evaluated reasonably fast.
    The real tricky thing is to determine suitable subranges and the
    parameters for their approximating polynomials. I have no idea
    at all how this done.
    --
    <mailto:> <http://www.dietmar-kuehl.de/>
    <http://www.eai-systems.com> - Efficient Artificial Intelligence
    Dietmar Kuehl, Dec 9, 2005
    #3
  4. Gerald

    Earl Purple Guest

    Dietmar Kuehl wrote:
    > I haven't implemented these functions myself and thus I might be
    > entirely wrong about how I think these functions are implemented.
    > Still, my understanding is that they are implemented very different
    > from how you tried to implement them. The basic approach is something
    > like this:
    >
    > 1. Translate the function argument(s) to a minimal basic area (this
    > is almost certainly not the correct term but I don't know the
    > correct term). My maths is rather rusty but I think for arctan(x)
    > the basic area is the range [0, 1]: all other values can be
    > derived from an appropriate argument:
    > - x < 0: arctan(x) = -arctan(-x)
    > - 1 < x: arctan(1/x) = pi/2 - arctan(x)
    > (actually, you already do this part...)
    > 2. For the values in basic area you look up the subrange your value
    > is located in. Each subrange is associated with an approximation
    > function which is just a suitably parameterized polynomial of a
    > relatively small degree which can be evaluated reasonably fast.
    > The real tricky thing is to determine suitable subranges and the
    > parameters for their approximating polynomials. I have no idea
    > at all how this done.
    > --
    > <mailto:> <http://www.dietmar-kuehl.de/>
    > <http://www.eai-systems.com> - Efficient Artificial Intelligence


    For good accuracy use cubic splines. For optimal speed use a bigger
    caching table and linear progression between the points. (A cubic
    spline has 4 parameters in each range so using the linear version you
    can store in theory 5 times as many points).
    Earl Purple, Dec 9, 2005
    #4
  5. Gerald

    Earl Purple Guest

    Of course you don't have to store the cubic spline parameters as they
    can be worked out
    from the cached value, but that would give you even slower performance.
    Earl Purple, Dec 9, 2005
    #5
  6. Gerald

    Guest

    Dietmar Kuehl wrote:
    > Gerald wrote:
    > > Recently, my program need to be run in embeded enviroment, and I cann't
    > > use standard library.
    > > But I need to use arctan(x)

    > The basic approach is something like this:
    >
    > 1. Translate the function argument(s) to a minimal basic area (this
    > is almost certainly not the correct term but I don't know the
    > correct term). My maths is rather rusty but I think for arctan(x)
    > the basic area is the range [0, 1]: all other values can be
    > derived from an appropriate argument:
    > - x < 0: arctan(x) = -arctan(-x)
    > - 1 < x: arctan(1/x) = pi/2 - arctan(x)
    > (actually, you already do this part...)


    There are two kinds of reductions. The first one is to keep the tables
    finite
    (This is essential for e.g. sin(x), as x may be any value) and the
    second is
    just to reduce the table size. The latter is something to worry about
    later.
    (It's a classic time/space tradeoff you'd need to profile).

    > 2. For the values in basic area you look up the subrange your value
    > is located in. Each subrange is associated with an approximation
    > function which is just a suitably parameterized polynomial of a
    > relatively small degree which can be evaluated reasonably fast.
    > The real tricky thing is to determine suitable subranges and the
    > parameters for their approximating polynomials. I have no idea
    > at all how this done.


    Polynomials are very efficient in finding the first few digits, but may
    be terrible
    in finding the next. E.g. when you already have arctan(x)=0.23....
    you'd need
    to look in table 23 to get the next coefficients, which implies 100
    tables.
    That's nog good for embedded systems. (Of course, real systems probably
    use nibbles not digits, so you'd need 256 tables after the first two
    nibbles)

    However, it seems a real arctan algorithm is a lot more complex:
    http://www.electronics.dit.ie/staff/aschwarzbacher/research/ecs99.pdf

    I wouldn't invent that myselves. Implementing the basic CORDIC seems
    easy, though.

    HTH,
    Michiel Salters
    , Dec 9, 2005
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Marc Schellens

    arctan of complex number

    Marc Schellens, Nov 26, 2003, in forum: C++
    Replies:
    8
    Views:
    6,116
    Gianni Mariani
    Nov 27, 2003
  2. Shi Mu
    Replies:
    8
    Views:
    19,409
    Robert Kern
    Nov 8, 2005
  3. Simon Brunning
    Replies:
    0
    Views:
    398
    Simon Brunning
    Nov 8, 2005
  4. Gerald
    Replies:
    0
    Views:
    698
    Gerald
    Dec 9, 2005
  5. Replies:
    3
    Views:
    2,408
Loading...

Share This Page