NXC: Fast Fourier Transformation (FFT) for NXT
NXC: Fast Fourier Transformation (FFT) for NXT
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
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
Last edited by HaWe on 20 Aug 2011, 11:16, edited 5 times in total.
Re: NXC: Fast Fourier Transformation (FFT) for NXT
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?
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?
-
- Posts: 358
- Joined: 01 Oct 2010, 06:37
- Location: Denmark
- Contact:
Re: NXC: Fast Fourier Transformation (FFT) for NXT
Notice your function calls:
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.
Code: Select all
void FillArraySin(float &x[], float &y[], int ArrLen)
(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.
My blog: http://spillerrec.dk/category/lego/
RICcreator, an alternative to nxtRICeditV2: http://riccreator.sourceforge.net/
RICcreator, an alternative to nxtRICeditV2: http://riccreator.sourceforge.net/
Re: NXC: Fast Fourier Transformation (FFT) for NXT
oh my God!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.
but that was the reason WHY I passed the variables "by reference", not "by value"!
what a mess...
Re: NXC: Fast Fourier Transformation (FFT) for NXT
never mind
Last edited by linusa on 30 Jun 2011, 17:02, edited 1 time in total.
RWTH - Mindstorms NXT Toolbox for MATLAB
state of the art in nxt remote control programming
http://www.mindstorms.rwth-aachen.de
MotorControl now also in Python, .net, and Mathematica
state of the art in nxt remote control programming
http://www.mindstorms.rwth-aachen.de
MotorControl now also in Python, .net, and Mathematica
Re: NXC: Fast Fourier Transformation (FFT) for NXT
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 !
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 !
Re: NXC: Fast Fourier Transformation (FFT) for NXT
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
http://www.mindstormsforum.de/viewtopic ... =24#p56252
Last edited by HaWe on 20 Aug 2011, 11:17, edited 9 times in total.
-
- Posts: 358
- Joined: 01 Oct 2010, 06:37
- Location: Denmark
- Contact:
Re: NXC: Fast Fourier Transformation (FFT) for NXT
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...doc-helmut wrote: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, 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.)doc-helmut wrote:I think the only way is to sacrifice all local variables and define only 1 global variable each.
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.
My blog: http://spillerrec.dk/category/lego/
RICcreator, an alternative to nxtRICeditV2: http://riccreator.sourceforge.net/
RICcreator, an alternative to nxtRICeditV2: http://riccreator.sourceforge.net/
Re: NXC: Fast Fourier Transformation (FFT) for NXT
anyone who likes to speed up the FFT by NBC?^^
(just the FFT function itself, not the rest for testing)
(just the FFT function itself, not the rest for testing)
-
- Posts: 358
- Joined: 01 Oct 2010, 06:37
- Location: Denmark
- Contact:
Re: NXC: Fast Fourier Transformation (FFT) for NXT
Try to optimize your function first, then convert it to NBC where significant gains can be archived.
For example this part:Perhaps you can calculate k instead of using a while loop?
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.
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;
}
Code: Select all
t1 = u1 * fx_[i1] - u2 * fy_[i1];
t2 = u1 * fy_[i1] + u2 * fx_[i1];
My blog: http://spillerrec.dk/category/lego/
RICcreator, an alternative to nxtRICeditV2: http://riccreator.sourceforge.net/
RICcreator, an alternative to nxtRICeditV2: http://riccreator.sourceforge.net/
Who is online
Users browsing this forum: Semrush [Bot] and 1 guest