BTW any chance of a look at that interesting sounding FFT app? Do you do the FFT in Basic4ppc code - if so it should speed up a lot, with minor amendments, with the next version of Basic4ppc that supports typed variables.
Sure, it's working well and relibale as a protoype, but it isn't finished yet.
The goal is to record a working radio-controlled heli, and to determine the speed at which the 2 main rotorblades are turning, somewhere between 1000 and 4000 RPM. I use 2^12=4096 bytes of a wave recording for that. I'll post more when it's finished.
But I have terrible performance problems, as you guessed:
On the desktop, the calculations are done in less then a second with a decent PC, but on a HTC Touch HD, it takes well over 2 minutes :-(
I really need to get it down to an acceptable amount of time for the end-user, something like a few seconds or so.
The core of the calculations, the FFT transformation, looks like this:
(the first part, the bit reversal is fast enough, but the second part is very slow). After that, there is some filtering and frequency peak detection to do, but that is the easy part.
Note: rawdata() contains the 4096 byte values from the wave file, rawdataIM() is empty in the beginning.
'THE FAST FOURIER TRANSFORM
'Upon entry, N=4096 contains the number of points in the DFT, rawdata() and
'rawdataIM() contain the real and imaginary parts of the input. Upon return,
'rawdata() and rawdataIM() contain the DFT output. All signals run from 0 to N-1.
NM1 = N-1
ND2 = N/2
M = Round(Log(N)/Log(2))
J = ND2
For i = 1 To (N-2) 'Bit reversal sorting
If i >= J Then Goto bit1
TR = rawdata(J)
TI = rawdataIM(J)
rawdata(J) = rawdata(i)
rawdataIM(J) = rawdataIM(i)
rawdata(i) = TR
rawdataIM(i) = TI
bit1:
K = ND2
bit2:
If K > J Then Goto bit3
J = J-K
K = K/2
Goto bit2
bit3:
J = J+K
Next i
For L = 1 To M 'Loop for each stage
LE = Round(2^L)
LE2 = LE/2
UR = 1
UI = 0
SR = Cos(cPI/LE2) 'Calculate sine & cosine values
SI = -Sin(cPI/LE2)
For J = 1 To LE2 'Loop for each sub DFT
JM1 = J-1
For i = JM1 To NM1 Step LE 'Loop for each butterfly
IP = i + LE2
TR = rawdata(IP)*UR-rawdataIM(IP)*UI 'Butterfly calculation
TI = rawdata(IP)*UI+rawdataIM(IP)* UR
rawdata(IP) = rawdata(i)-TR
rawdataIM(IP) = rawdataIM(i)-TI
rawdata(i) = rawdata(i)+TR
rawdataIM(i) = rawdataIM(i)+TI
Next i
TR = UR
UR = TR*SR-UI*SI
UI = TR*SI+UI*SR
Next J
Next L
Msgbox ("Ending FFT calculations")