The efficiency of arcsin calculations from the sine lookup table

Question

I executed a lookup table to calculate the sine / cosine values ​​on my system. Now I need inverse trigonometric functions (arcsin / arccos).

My application runs on an embedded device on which I cannot add a second lookup table for arcsin, since I am limited in program memory. So the solution I had in mind was to look at the sine lookup table to get the corresponding index.

I am wondering if this solution will be more efficient than using a standard implementation coming from a mathematical standard library.
Has anyone already experimented on this?

The current LUT implementation is an array of sine values ​​from 0 to PI / 2. The value stored in the table is multiplied by 4096 to stay with integer values ​​with sufficient accuracy for my application. A lookup table as a resolution of 1/4096, which gives us an array of 6434 values. Then I have two sine and cosine functionalities, which takes an angle in the radian, multiplied by 4096 as an argument. These functions convert the given angle to the corresponding angle in the first quadrant and read the corresponding value in the table.

My application runs on dsPIC33F at 40 MIPS and I use the C30 compilation set.

Answer 1

It’s hard to say anything with certainty, since you didn’t tell us about hardware, compiler or code. However, a priori, I would expect your compiler’s standard library to be more efficient than your code.

Answer 2

You may need to use the C30 compiler, which does not support C ++, otherwise I would point you to Optimizing Applications with Intensive Mathematics using Fixed Point Arithmetic and its associated library.

However, the general principles of the CORDIC algorithm apply, and the amount of memory will be much less than your current implementation. The article explains that the generation of arctan () and arccos () and arcsin () can be computed from this, as described here .

Of course, this also assumes that you will also need the square root and separation. They can be expensive, although PIC24 / dsPICs have hardware integer division. The article on mathematical acceleration also uses the square root. Your approach to the lookup table will probably be faster for direct searches, but maybe not for reverse searches, but the approaches described in this article are more general and more accurate (the library uses 64-bit integers as 36.28 bits fixed point , you can get away with less accuracy and range in your application), and, of course, faster than the standard library implementation using floating point software.

Answer 3

You can use the halfway approach by combining a coarse-grained lookup table to save memory and a numerical approximation for intermediate values ​​(like the Maclaurin Series , which will be more accurate than linear interpolation.)

Some examples are here .

This question also contains some related links.

Answer 4

Binary search 6434 will take ~ 12 searches to find the value, and then interpolation if more accuracy is required. Due to nature, if the curve is sin, you will get much more accuracy at one end than at the other. If you can save memory, make your own reverse table evenly distributed over the inputs, probably the best bet for speed and accuracy.

Compared to the built-in version, you will need to verify this. When you do this, pay attention to how large your image size is. On some systems, the implementation of stdin can be quite high.