C++ Fast Trigonometric Functions

Introduction

To improve algorithm performance, one direct way is to shorten calculation time. The part that consumes the most computation power would be the trig functions.

The built-in trig functions are generally very good in terms of accuracy. But we don’t need that level of precision, so we can sacrifice accuracy to achieve faster speed.

We only use SIN, COS, ACOS and ATAN in our algorithm, so this post will describe only these functions.

SIN and COS

One popular, easy and really fast way is to use look-up table.
Firstly I generated a list of 256 input from 0 to 360, with equal intervals, and get a list of results for each input.

and then use the list of results as our table, and input (in degree) as our index. so let’s say we need to get SIN(30), we just need to look up the 30th value in the table.

The reason that I use 1 degree instead of smaller interval, is that not only it saves spaces, but also I won’t need that kind of precision. we can obviously do smaller interval like 0.5, or 0.2. just do some index conversion before looking up.

Actually, we don’t need the full cycle of SIN, we just need the first quarter cycle, because the whole cycle can be replicated by the first quarter, so we save a lot of memory! All we have to do is to add some if/else statements, and do some tricks on the index system.

Since SIN and COS are very close brothers (or sisters), that COS is just a shifted version of SIN, and we can lookup its value from the same table. The difference is just on the indexing.

Because we are only using integer degree input, and the result for it was computed from the built-in SIN function, so it’s guaranteed to be correct!

[Upload Source Code]
ACOS

ACOS is different, because input will be between -1 and 1, if we are going to use look-up table, we will need to do index conversion that involves multiplication and division which will kill the performance. Also the table need to be huge because we can’t reduce table size like what we did in the SIN function. So might be better to use infinite series stated here.

It should be noted that the more accurate, the higher power term needs to be computed. Power is a terrible performance killer, so I will only keep the first 4 terms.

To verify the accuracy, we can compare the built-in method with the ‘polynomial’ method in Excel.

As we can see, the error rises exponentially after about 0.3. It is obvious what we have a larger error as we go near 1. Because we are only keeping the first few polynomial terms, as we go nearer to 1, the neglected terms will become significant, thus making the difference obvious.

what we can do here, is to replace the polynomial method with look-up table, let say when input is larger than 0.8, when the error could have reached about 1%.

New method is about 15 times faster! (measured in VC++)

[Upload Source Code]
ATAN

I have been search for a way to do it. But none seems to be faster than C++ ATAN. So I will stick with it for now.

You can now find the library in GitHub (not my account).

6 thoughts on “C++ Fast Trigonometric Functions

  1. TTN

    I’m also on the same boat. I’m building a 3d delta printer using a arduino mega with ramps1.4.
    It’s using inverse kinematics to move ( pastebin.com/pw7EkTuB) . As of now, the arduino can only handle 40 segments per second, which at a 40mm/sec would give 1mm segments in prints. Far too large. I guess my question is did you try the lookup table method or something else?

    Reply
      1. TTN

        I implemented a lookup table for atan on the arduino mega, and it is ever so slightly slower surprisingly. Details are the project page: hackaday.io/project/1565-icepick-delta/log/12049-arc-tangent-lookup-function

Leave a Reply

Your email address will not be published. Required fields are marked *

Are you Robot? *

I only check blog comments once or twice a week, if you want a quick reply you can post your question on this forum IntoFPV.com... You might get a faster response from me there (multirotor related only).