Simple trigonometric algorithm to compute sin() and cos() of fixed-point numbers

Question

As I showed in other questions, i'm currently implementing a C++ metaprogramming library which includes, among other things, a set of types and metafunctions for compile-time arithmetic.

My goal now is to implement the trigonometric functions sin and cos for my fixed point type.
My problem is that every paper I have found about trigonometric algorithms talks about CORDIC or some kind of Taylor series. The problem with CORDIC is that it needs a huge set of precomputed values through a lookup-table, and I couln't provide it easilly with tmp. Also, the point of CORDIC is to compute that trigonometric functions in hardware which has not a multiplier, and i'm perfectly cappable to do multiplications with my library.

So my question is: Is there any other simple alternative to CORDIC and Taylor Series to compute trigonometric functions?

Why not use a polynomial approximation based on the Taylor series? — Patricia Shanahan, Sep 12 '13 at 01:10
@PatriciaShanahan I'm worried about the template-instantation-depth necesary to compute the polynomial — Manu343726, Sep 12 '13 at 01:14
[A similar question](http://stackoverflow.com/questions/18662261/fastest-implementation-of-sine-cosine-and-square-root-in-c-doesnt-need-to-b) came up a few days ago and one of the comments gave this link: http://devmaster.net/posts/9648/fast-and-accurate-sine-cosine — Mark Ransom, Sep 12 '13 at 01:39
suggest reading my article on Chebyshev approximations: https://www.embeddedrelated.com/showarticle/152.php — Jason S, Mar 30 '20 at 16:07

score 3 · Accepted Answer · edited Jan 10 '18 at 04:09

Finally I have implemented the sin metafunction through Taylor series, using series of 10 terms by default (Could be configurable). I have based my implementation in this interesting article.

My library includes an implementation of a tmp for loop using iterators, and expression templates to allow write complex expressions in a "clear" way (Clear compared to the common template-meta-programming syntax add<mul<sub<1,2>>>...). This allows me to literally copy-paste the C implementation provided by the article:

template<typename T , typename TERMS_COUNT = mpl::uinteger<4>>
struct sin_t;

template<typename T , typename TERMS_COUNT = mpl::uinteger<4>>
using sin = typename sin_t<T,TERMS_COUNT>::result;

/*
 * sin() function implementation through Taylor series (Check http://www10.informatik.uni-erlangen.de/~pflaum/pflaum/ProSeminar/meta-art.html)
 * 
 * The C equivalent code is:
 * 
 * // Calculate sin(x) using j terms
 * float sine(float x, int j)
 * {
 *     float val = 1;
 *
 *     for (int k = j - 1; k >= 0; --k)
 *         val = 1 - x*x/(2*k+2)/(2*k+3)*val;
 *
 *     return x * val;
 * }
 */

template<mpl::fpbits BITS , mpl::fbcount PRECISION , unsigned int TERMS_COUNT>
struct sin_t<mpl::fixed_point<BITS,PRECISION>,mpl::uinteger<TERMS_COUNT>>
{
private:
    using x = mpl::fixed_point<BITS,PRECISION>;

    using begin = mpl::make_integer_backward_iterator<TERMS_COUNT-1>;
    using end   = mpl::make_integer_backward_iterator<-1>;

    using one   = mpl::decimal<1,0,PRECISION>;
    using two   = mpl::decimal<2,0,PRECISION>;
    using three = mpl::decimal<3,0,PRECISION>;

    template<typename K , typename VAL>
    struct kernel : public mpl::function<decltype( one() - ( x() * x() )/(two() * K() + two())/(two()*K()+three())*VAL() )> {};

public:
    using result = decltype( x() * mpl::for_loop<begin , end , one , kernel>() );
};

Here is the header of the implementation in the project repo.

you can do much better than Taylor series – Jason S Mar 30 '20 at 16:07 — Jason S, Mar 30 '20 at 16:07

score 2 · Answer 2 · answered Sep 12 '13 at 01:14

huge set of precomputed values through a lookup-table

How many is "huge"? Sounds like a one-time effort that would be fast as hell once you were done. My advice? Get a shovel and fill in that table. You'd have it done by the time you get another answer here.

Simple trigonometric algorithm to compute sin() and cos() of fixed-point numbers

2 Answers2