Twiddle table computing

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?

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.

StackExchange Code Review Q#147830, answer score: 10