Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I want to calculate y(n)=32677Sin(45/1024•n), where y is an integer and n ranges from 0 to 2048. How can I make this process quicker and more precisely? Now I want to show you a reference answer: Since Sin(a+b)=Sin(a)Cos(b)+Cos(a)Sin(b) And Cos(a+b)=Cos(a)Cos(b)-Sin(a)Cos(b). So I can store Sin(45/1024•1) and Cos(45/1024•1) only.Then use this formula:

Sin(45/1024•2)=Sin(45/1024•1+45/1024•1), Cos(45/1024•2)=Cos(45/1024•1+45/1024•1), Sin(45/1024•n)=Sin(45/1024•(n-1)+45/1024•1), Cos(45/1024•n)=Cos(45/1024•(n-1)+45/1024•1) , This way maybe quicker without storing large array.

share|improve this question
    
This question is appropriate for Programmers, assuming the intention is to learn about the appropriate algorithms and/or data structures from the perspective of software engineering concerns. –  Thomas Owens Oct 8 '12 at 13:19
8  
That 45 is a bit suspect; it makes me think you want sin(x) where x is in degrees. If that's the case, you need to be aware that the argument to the trig functions is typically in radians. The argument is in radians in C++, which is how this question is tagged. –  David Hammen Oct 8 '12 at 14:19
    
Why do you need this question answered? What's the application? –  GlenPeterson Oct 9 '12 at 0:00
    
How accurate do you need the result to be? –  dan04 Oct 9 '12 at 2:06
    
@dan04 Since y is an integer, I need it accurate as an integer . –  LaiJong Oct 9 '12 at 4:03
show 2 more comments

3 Answers 3

If n ranges from 0 to 2048, you can pre-calculate the values, store then in an array. y(n) would become values[n].

share|improve this answer
    
+1 and you can interpolate for any values in between (if that's a possibility). –  Daniel B Oct 8 '12 at 13:19
1  
That's a viable option, though I'd still profile it to make sure it is more efficient than calculating it (e.g. the FPU's fsin might be used and be more cache-friendly than some array). –  Benjamin Bannier Oct 8 '12 at 13:20
    
How about not storing value[n]? –  LaiJong Oct 8 '12 at 13:24
2  
Trigonometric functions are very slow to compute on the fly. I'm pretty sure every fast implementation uses pre-computed values. Since sin() and cos() are periodic, you only need to store the first 90 degrees. You can return -sin(), or sin(90 - the angle), or -sin(90 - the angle) depending on the quadrant. You can also define cos() in terms of sin(). If you know the possible range of input values, you can pre-compute and only store the values you need for your program. If not, interpolation between a limited number of values may be your fastest option. –  GlenPeterson Oct 8 '12 at 13:39
1  
@Glen: Sin values are between -1 and 1, so it will actually fit in 16-bit unsigned. –  vartec Oct 9 '12 at 9:20
show 5 more comments

Given the form of the function, the natural answer is the CORDIC algorithm. It's a much cleaner approach than the breakdown in the question. On the other hand, the table it needs is far, far smaller than the table others have suggested.

share|improve this answer
add comment

Compute the table at compile time instead of run time.

You're doing a 2048-element table of 16-bit scaled integer values.

Write a cheap Matlab script, with a print that gives a data line suitable for your final programming language. Cut-and-paste the result into your source code, as a constant data table, and do a table lookup at run time. This pushes the initial computation time off into the build cycle, instead of the program startup time.

share|improve this answer
    
How much runtime does this save compared to the extra programmer cost? –  JBRWilkinson Oct 8 '12 at 21:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.