NXC: Fast Fourier Transformation (FFT) for NXT

[HaWe]

hi,
this is my Fast Fourier Transformation (FFT) for NXC. Many thanks to hergipotter who was so kind to explain the underlying maths to me :)

For demonstration an array[32] is filled with values from a sinus function by the test function FillArraySin(...)
(as the FFT calculates by complex numbers, it's actually TWO arrays, x[] for real parts and y[] for imaginary parts).

Other FillArray functions for testing are already implemented.

Be sure that for larger customized arrays the size has to be a power of 2! (16, 32, 64, 128,...)

share and enjoy!
http://www.mindstormsforum.de/viewtopic ... =24#p56252

[HaWe]

and straightway 1 question:
I tested it fine with array lengths up to 512, but for 1024 I get a file error -5
Is this probably because of too little memory?
Actually for the memory it should be fine: 1024 * 4 byte * 2 arrays = 8 kbyte ?
or do I miss sth?

[spillerrec]

Notice your function calls:

Code: Select all

void FillArraySin(float &x[], float &y[], int ArrLen)

In C this passes the variable by reference. However NBC does not have any concepts of pointers or the like so this is impossible. Instead it creates a variable x and copies the variable you want to pass into that. When the function returns, it copies the contents of x back into the variable you passed it.
(Normal functions do the same, they just don't copy them back again.)

So you don't just have 2 arrays, you have 2 arrays + 2 * amount_of_functions (which you pass both arrays). And it looks like you are calling 3 functions, so that is 2 + 2 * 3 = 8 which becomes 32kB.

[HaWe]

Instead it creates a variable x and copies the variable you want to pass into that. When the function returns, it copies the contents of x back into the variable you passed it.

oh my God!
but that was the reason WHY I passed the variables "by reference", not "by value"!
what a mess...

[linusa]

never mind

[HaWe]

I changed the parameters of the PrintArray function from "by value" to "by reference" (the only ones which I had accidentally left as "by value").
Now I have the "pass by reference" everywhere - and it really makes no difference: still memory error -5.

I think the only way is to sacrifice all local variables and define only 1 global variable each.

That issue is really worth while an enhanced change of the fw !

[HaWe]

now I'm using only 2 global arrays, and now it works fine with an array length up to 2048:
http://www.mindstormsforum.de/viewtopic ... =24#p56252

[spillerrec]

I changed the parameters of the PrintArray function from "by value" to "by reference" (the only ones which I had accidentally left as "by value").
Now I have the "pass by reference" everywhere - and it really makes no difference: still memory error -5.

Yes, it makes no difference because "by reference" is just "by value" with a twist in NXC. There is no way to improve this other than trying to share variables between functions and this cannot be done safely without checking which treads they are running in and which function calls them. The current compiler is sadly nowhere sophisticated enough to do this kind of optimization so don't expect this to happen...

I think the only way is to sacrifice all local variables and define only 1 global variable each.

Yes, this is the best workaround. It is not pretty but will improve efficiency both in memory consumption and rxe size. (rxe size is affected mostly if you are passing structures which needs to be declared for each variable.)
I would really like to be able to declare global variable as static, since this limits the scope of the variable to the current source file. This would make it easier to make efficient libraries without the risk of name collisions.

[HaWe]

anyone who likes to speed up the FFT by NBC?^^
(just the FFT function itself, not the rest for testing)

[spillerrec]

Try to optimize your function first, then convert it to NBC where significant gains can be archived.

For example this part:

Code: Select all

   /* Do the bit reversal */
   i2 = nn >> 1;
   j = 0;
   for (i=0;i<nn-1;i++) {
      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;
   }

Perhaps you can calculate k instead of using a while loop?

Code: Select all

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

Notice here that you are using fx_[i1] twice. (Same with fy_[i1].) Store the value of fx_[i1] in a variable as otherwise it will spend time looking it up in the array each time you try to access it.