Trigonometric functions on embedded system

Question

sin and cos functions are slow and need a lot of resources to run on embedded systems. How does one calculate sin and cos functions in a more resource-saving and faster way?

Answer 1

To calculate a Taylor or Fourier series is always going to be time-consuming.

In an embedded system, you should think about lookup tables.

There might also be interesting information on the 'Net about how Hewlett-Packard optimised such calculations in their early scientific calculators.

I recall seeing such stuff at the time

Answer 2

There seems to be an nice pseudocode example here and explicit code here.

However, as @unwind suggested, you might want to try to precalculate these tables on a decent computer and load the tables to the embedded device.

If your answer doesn't have to be very exact, the lookup table would be rather small, and you'll be able to store it in your device's memory. If you need higher accuracy, you'll need to calculate it within the device. It's a tradeoff between memory, time and required precision; the answer relies on the specific nature of your project.

Answer 3

1. Lookup-tables
2. Taylor series, like you say

Note that with lookup-tables, you can often optimize things by limiting the domain, e.g. represent the angle as an unsigned char, giving you only 256 steps around the circle but also a very compact table. Similar things can be done to the value, like using fixed-point.

Answer 4

Depends on what you need it for. If you are not very fussed about your angle accuracy (e.g. if to the nearest degree is OK) then just use a lookup table of values. If you don't have an FPU, work in fixed-point.

One simple way to calculate sin/cos functions is with Taylor series (as shown under Trigonometric Functions here). The fewer terms you use, the less accurate the values but the faster the calculations.

Fourier series calculations require some sin/cos values to be known. If you store things in the frequency domain most of the time, though, you can potentially save on calculations - depending on what it is you are doing.

Answer 5

A lookup table with interpolation would without doubt be the most efficient solution. If you want to use less memory however, CORDIC is a pretty efficient algorithm for calculating values of trig functions, and is commonly implemented in handheld calculators.

As a side point, it doesn't make any sense to represent these functions using fourier series, since you're just creating a circular problem of how you then evaluate the sin/cos terms of series. A Taylor series is a well-known approximation method, but the error turns out to be unacceptably large in many cases.

You may also want to check out this question and its answers, regarding fast trigonometric functions for Java (thus the code could be ported easily). It mentions both the CORDIC and Chebyshev approximations, among others. One of them will undoubtedly suit your needs.

Answer 6

See the Stack Overflow question How do Trigonometric functions work? The accepted answer there explains some details of how to do range reduction, then use CORDIC, then do some further optimizations.

Answer 7

This Dr. Dobb's article: Optimizing Math-Intensive Applications with Fixed-Point Arithmetic has a good explanation of CORDIC algorithms and provides complete source code for the library discussed in the article.

Answer 8

In some cases one can manage with just IIR filter, tuned to resonance on needed frequency. Look here: http://www.ee.ic.ac.uk/pcheung/teaching/ee3_Study_Project/Sinewave%20Generation(708).pdf