4

I have implemented a lookup table to compute sine/cosine values in my system. I now need inverse trigonometric functions (arcsin/arccos).

My application is running on an embedded device on which I can't add a second lookup table for arcsin as I am limited in program memory. So the solution I had in mind was to browse over the sine lookup table to retrieve the corresponding index.

I am wondering if this solution will be more efficient than using the standard implementation coming from the math standard library.
Has someone already experimented on this?

The current implementation of the LUT is an array of the sine values from 0 to PI/2. The value stored in the table are multiplied by 4096 to stay with integer values with enough precision for my application. The lookup table as a resolution of 1/4096 which give us an array of 6434 values. Then I have two funcitons sine & cosine that takes an angle in radian multiplied by 4096 as argument. Those 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 an I use the C30 compiling suite.

greydet
  • 5,509
  • 3
  • 31
  • 51
  • 3
    Please describe the structure of your current sine/cosine table – finnw May 07 '11 at 10:37
  • Agreeing with finnw. Depending on the structure of your table now, you might do a binary search over the table which might be fast enough. But you'll also lose more or less accuracy this way. – schnaader May 07 '11 at 10:55
  • I edited my question with information on my lookup table implementation – greydet May 07 '11 at 11:58

4 Answers4

3

It's pretty hard to say anything with certainty since you have not told us about the hardware, the compiler or your code. However, a priori, I'd expect the standard library from your compiler to be more efficient than your code.

David Heffernan
  • 601,492
  • 42
  • 1,072
  • 1,490
3

It is perhaps unfortunate that you have to use the C30 compiler which does not support C++, otherwise I'd point you to Optimizing Math-Intensive Applications with Fixed-Point Arithmetic and its associated library.

However the general principles of the CORDIC algorithm apply, and the memory footprint will be far smaller than your current implementation. The article explains the generation of arctan() and the arccos() and arcsin() can be calculated from that as described here.

enter image description here

enter image description here

Of course that suggests also that you will need square-root and division also. These may be expensive though PIC24/dsPIC have hardware integer division. The article on math acceleration deals with square-root also. It is likely that your look-up table approach will be faster for the direct look-up, but perhaps not for the reverse search, but the approaches explained in this article are more general and more precise (the library uses 64bit integers as 36.28 bit fixed point, you might get away with less precision and range in your application), and certainly faster than a standard library implementation using software-floating-point.

Clifford
  • 88,407
  • 13
  • 85
  • 165
2

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

Some examples here.

This question also has some related links.

Community
  • 1
  • 1
finnw
  • 47,861
  • 24
  • 143
  • 221
0

A binary search of 6434 will take ~12 lookups to find the value, followed by an interpolation if more accuracy is needed. Due to the nature if the sin curve, you will get much more accuracy at one end than the other. If you can spare the memory, making your own inverse table evenly spaced on the inputs is likely a better bet for speed and accuracy.

In terms of comparison to the built-in version, you'll have to test that. When you do, pay attention to how much the size of your image increases. The stdin implementations can be pretty hefty in some systems.

AShelly
  • 34,686
  • 15
  • 91
  • 152
  • Oops I missed the line where you said you can't afford the 2nd table. I'd still see what savings you can get by removing the stdlib d – AShelly May 07 '11 at 18:35