current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 4 down vote favorite

I'm trying to optimize this twiddle computing function:

void twiddle(int N)
{
  int i;
  for (i=0;i<N;i++)
  {
     twiddle_table[i].re = (float)   cos((float)i * 2.0 * PI /(float)N);
     twiddle_table[i].im = (float) - sin((float)i * 2.0 * PI /(float)N);
  }
}

where N = 4096 size of twiddle table and could be bigger!

And then, I did the following:

void twiddle(int N)
{
   int i;
   float Tconst;
   Tconst = 2.0 * PI /(float)N;
   for (i=0;i<N;i++)
   {
      twiddle_table[i].re = (float)   cos((float)i * Tconst);
      twiddle_table[i].im = (float) - sin((float)i * Tconst);
   }
}

But, I'm getting a performance of 340,000 cycles for the for loop, which I think is bad.

Any hints that could enhance the performance of this function?

share|improve this question
2  
Your question is quite unclear. What does it mean to "twiddle" something? Where is your twiddle_table defined? You didn't show all of your code. Also, what does 340 000 cycles for the for loop mean, when we don't even know the value of N or the size of the twiddle_table? – Justin 12 hours ago
1  
While the OP certainly should have explained himself, Google quickly told me that "twiddle table" is an established jargon term related to the implementation of FFTs (fast Fourier transforms). See e.g. en.wikipedia.org/wiki/Twiddle_factor – Quuxplusone 11 hours ago
    
this line: Tconst = 2.0 * PI /(float)N; will be performed in double due to the 2.0 to perform it in float, change the 2.0 to 2.0f – user3629249 6 hours ago
    
extract the expression: (float)i*Tconst to assign a float variable, inside the top of the for() loop and use that variable in the actual calculations – user3629249 6 hours ago
    
please show the definition of: twiddle_table[] – user3629249 6 hours ago
up vote 8 down vote

The optimization you made manually is most likely already noticed and implemented by the compiler.

Instead, you should notice that \$\cos\frac{2\pi k}{N} - i \sin\frac{2\pi k}{N} = e^{-\frac{2\pi i}{N}k}\$, and replace multiple invocations of sin and cos with multiplications. Naively:

    complex base = { cos(2.0 * PI / N), -sin(2.0 * PI / N) };
    twiddle_table[0] = { 1.0, 0.0 };
    for (i = 1; i < N; ++i) {
        twiddle_table[i] = twiddle_table[i - 1] * base;
    }

In the production code you need to pay attention to the accumulation of numerical errors, and once in a while fall back to direct computation of sin and cos (or cexp).

Of course, if your compiler doesn't support complex type, you's have to implement complex multiplication manually.

Another optimization comes from the inherent symmetry of the table, e.g. \$cos\frac{2\pi k}{N} = \cos\frac{2\pi (N - k)}{N}\$, so you only need to compute half of the table; there are more symmetries you may exploit.

PS: That said, I strongly recommend to precompute it once for largest possible N. Notice that it can be reused for any power of 2.

share|improve this answer
    
"In the production code you need to pay attention to the accumulation of numerical errors," - this is VERY important as multiplication quickly grows the error! – RobAu 3 hours ago

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.