Create Fast Sin () function to improve fps? Fast sin () function?

Question

I make 500x500 dots in real time. I have to calculate the position of the points using the atan () and sin () functions. Using atan () and sin (), I get 24 fps (frames per second).

float thetaC = atan(value); float h = (value) / (sin(thetaC))); 

If I do not use sin (), I get 52 fps .

and if I do not use atan (), I am 30 fps .

So the big problem is with sin (). How to use the Fast Sin version. Can I create a Look Up table for this? I do not have any specific values ​​for creating a LUT. what can i do in this situation?

PS: I also tried ASM's quick sin function, but I get no difference.

Thanks.

Answer 1

It depends on the required accuracy. The maximum derivative of sin is 1, so if x1 and x2 are inside epsilon from each other, then sin (x1) and sin (x2) are also inside epsilon. If you only want accuracy, say 0.001, then you can create a lookup table of 1000 * PI = 3142 points and just look at the value closest to the one you need. This can be faster than what the native code does, since the native code (possibly) uses a lookup table for polynomial coefficients and then interpolates, and since this table can be small enough to stay in the cache easily.

If you need full accuracy over the entire range, then there is probably nothing better than what you can do.

If you want, you can also create a lookup table (1 / sin (x)), as this is your actual function of interest. In any case, you need to be careful around sin (x) = 0, since a small error in sin (x) can cause a big error in 1 / sin (x). Determining the tolerance of errors is important in determining which shortcuts you can use.

You will create a lookup table with something like:

 float *table = malloc(1000 * sizeof(float)); for(int i = 0; i < 1000; i++){ table[i] = sin(i/1000.0); } 

and get to him something like

 void fastSin(float x){ int index = x * 1000.0; return table[index]; } 

This code is not complete (and will break into anything outside 0 <x <1 due to array limitations), but should start working.

Answer 2

Wait a second....

You have a triangle, you calculate the hypotenuse. First, you take atan(value) to get the angle, and then again using value with sin to calculate h . So, we have a scenario where one side of the triangle is 1:

  /| h / | value / | /C__| 1 

All you really need to do is calculate h = sqrt(value*value + 1); ... But then sqrt not the fastest function around.

Perhaps I missed this moment or you left something. I always used lookup tables for sin and cos and found them fast. If you don't know the value in advance, you need to get closer, but that means multiplication, truncation to an integer (and possibly sign conversion) to get the index of the array. If you can convert your units to integers (effectively making your floats a fixed point), this makes the search even faster.

Answer 3

For sin (but not atan) you can become simpler than a table - just create

 float sin_arr[31416]; //Or as much precision as you need for (int i=0; i<31416; ++i) sin_arr[i] = sin( i / 10000.0 ); //... float h = (value) / sin_arr[ (int)(thetaC*10000.0) % 31416 ]; 

I guess this will give you speed improvement.

Answer 4

I happened to stumble upon this open source JavaScript library, which includes an interesting approximation of trigonometric functions (sin and tan among others). It seems to be fast and accurate.
Perhaps you could rewrite it in c / C ++.
Library: http://danisraelmalta.imtqy.com/Fmath/