fft.txt

fft

Public Sub fft(pr() As Single, pi() As Single, N As Long, k As Long, fr() As Single, fi() As Single, ll As Long, ill As Long)

Dim it As Long, i As Long, j As Long
Dim m As Long, iis As Long, nv As Long, ll0 As Long
Dim p As Single, q As Single, s As Single
Dim vr As Single, vi As Single, poddr As Single, poddi As Single

For it = 0 To N - 1
m = it
iis = 0
For i = 0 To k - 1
j = m \ 2
iis = 2 * iis + (m - 2 * j)
m = j
Next i
fr(it) = pr(iis)
fi(it) = pi(iis)
Next it

pr(0) = 1#
pi(0) = 0#
p = 6.283185306 / (1# * N)
pr(1) = Cos(p)
pi(1) = -Sin(p)
If (ll <> 0) Then
pi(1) = -pi(1)
End If

For i = 2 To N - 1
p = pr(i - 1) * pr(1)
q = pi(i - 1) * pi(1)
s = (pr(i - 1) + pi(i - 1)) * (pr(1) + pi(1))
pr(i) = p - q
pi(i) = s - p - q
Next i

For it = 0 To N - 2 Step 2
vr = fr(it)
vi = fi(it)
fr(it) = vr + fr(it + 1)
fi(it) = vi + fi(it + 1)
fr(it + 1) = vr - fr(it + 1)
fi(it + 1) = vi - fi(it + 1)
Next it

m = N \ 2
nv = 2

For ll0 = k - 2 To 0 Step -1
m = m \ 2
nv = 2 * nv
For it = 0 To (m - 1) * nv Step nv
For j = 0 To (nv \ 2 - 1)
p = pr(m * j) * fr(it + j + nv \ 2)
q = pi(m * j) * fi(it + j + nv \ 2)
s = pr(m * j) + pi(m * j)
s = s * (fr(it + j + nv \ 2) + fi(it + j + nv \ 2))
poddr = p - q
poddi = s - p - q
fr(it + j + nv \ 2) = fr(it + j) - poddr
fi(it + j + nv \ 2) = fi(it + j) - poddi
fr(it + j) = fr(it + j) + poddr
fi(it + j) = fi(it + j) + poddi
Next j
Next it
Next ll0

If (ll <> 0) Then
For i = 0 To N - 1
fr(i) = fr(i) / (1# * N)
fi(i) = fi(i) / (1# * N)
Next i
End If

If (ill <> 0) Then
For i = 0 To N - 1
pr(i) = Sqr(fr(i) * fr(i) + fi(i) * fi(i))
If Abs(fr(i)) < 0.000001 * Abs(fi(i)) Then
If ((fi(i) * fr(i)) > 0) Then
pi(i) = 90#
Else
pi(i) = -90#
End If
Else
pi(i) = Atn(fi(i) / fr(i)) * 360# / 6.283185306
End If
Next i
End If
For i = 0 To N - 1
pr(i) = 2# * pr(i) / (N - 1)
Next
For i = 0 To N - 1
pi(i) = 2# * pi(i) / (N - 1)
Next

End Sub