NXC: Fast Fourier Transformation (FFT) for NXT

[HaWe]

the 1st: this way?

Code: Select all

   i=0;
   while (i<nn-1) {
      if (i < j) {
         tx = fx_[i];
         ty = fy_[i];
         fx_[i] = fx_[j];
         fy_[i] = fy_[j];
         fx_[j] = tx;
         fy_[j] = ty;
      }
      k = i2;
      while (k <= j) {
         j -= k;
         k >>= 1;
      }
      j += k;
      ++i;
   }

the 2nd: no problem:

Code: Select all

      for (i=j;i<nn;i+=l2) {
            i1 = i + l1;

            tx=fx_[i1];
            ty=fy_[i1];
            
            t1 = u1 * tx - u2 * ty ;
            t2 = u1 * ty + u2 * tx ;
            
            fx_[i1] = fx_[i] - t1;
            fy_[i1] = fy_[i] - t2;

            fx_[i] += t1;
            fy_[i] += t2;
      }

[spillerrec]

1:
No, that is not what I meant. I copied a bit too much though, it was just this section I meant:

Code: Select all

      k = i2;
      while (k <= j) {
         j -= k;
         k >>= 1;
      }
      j += k;

Perhaps, instead of using a loop, you could calculate j by calculate how many times the loop will run? (instead of actually doing it) This case looks a bit tricky, but it might be possible.
Something simpler:

Code: Select all

   nn = 1;
   for (i=0;i<m;i++)
      nn *= 2;[code]This loop will run m times, each time multiplying nn with 2. So nn will end up being 2^m. So you could either do "nn = pow( 2, m )" or "nn = 1 << m;" depending on what is fastest, avoiding a loop completely.

[HaWe]

doing such things I'm afraid I will corrupt the code.
But I expect for and while loops to be as stable and as fast enough just as they are. So I actually don't want to change them.