Platforms to show: All Mac Windows Linux Cross-Platform
Required plugins for this example: MBS DataTypes Plugin
You find this example project in your Plugins Download as a Xojo project file within the examples folder: /DataTypes/FFT
This example is the version from Sun, 17th Mar 2012.
Project "FFT.xojo_binary_project"
Class App Inherits Application
Const kEditClear = "&Delete"
Const kFileQuit = "&Quit"
Const kFileQuitShortcut = ""
End Class
Class Window1 Inherits Window
Control BevelButton1 Inherits BevelButton
ControlInstance BevelButton1 Inherits BevelButton
EventHandler Sub Action()
const NumberOfValues = 10000
dim valuesf(-1) as single
dim valuesd(-1) as Double
for i as integer = 1 to NumberOfValues
dim d as Double = rnd
valuesd.Append d
valuesf.Append d
next
// Double with RB Code
dim m1 as Double = Microseconds
dim c() as Complex = FFT_Suite.FFT(valuesd)
m1 = Microseconds - m1
dim u as integer = c.Ubound
if u>100 then u = 100
for x as integer = 0 to u
Listbox1.AddRow(str(c(x).Abs))
next
// Double with Plugin
dim m2 as Double = Microseconds
dim m() as double = FFTDoubleAbsMBS(valuesd)
m2 = Microseconds - m2
u = m.Ubound
if u>100 then u = 100
for x as integer = 0 to u
Listbox1.cell(x,1)=str(m(x))
next
// Single with Plugin
dim m3 as Double = Microseconds
dim f() as single = FFTSingleAbsMBS(valuesf)
m3 = Microseconds - m3
u = f.Ubound
if u>100 then u = 100
for x as integer = 0 to u
Listbox1.cell(x,2)=str(f(x))
next
StaticText1.text = Format(m1,"0")+" vs. "+Format(m2,"0")+" vs. "+Format(m3,"0")
End EventHandler
End Control
Control Listbox1 Inherits Listbox
ControlInstance Listbox1 Inherits Listbox
End Control
Control StaticText1 Inherits Label
ControlInstance StaticText1 Inherits Label
End Control
End Class
MenuBar MenuBar1
MenuItem FileMenu = "&File"
MenuItem FileQuit = "#App.kFileQuit"
MenuItem EditMenu = "&Edit"
MenuItem EditUndo = "&Undo"
MenuItem UntitledMenu1 = "-"
MenuItem EditCut = "Cu&t"
MenuItem EditCopy = "&Copy"
MenuItem EditPaste = "&Paste"
MenuItem EditClear = "#App.kEditClear"
MenuItem UntitledMenu0 = "-"
MenuItem EditSelectAll = "Select &All"
End MenuBar
Module FFT_Suite
Const pi = 3.141592653589793238462643383279502884197169399375105820974944592
Function FFT(x() as complex, N as integer = -1) As Complex()
// Zero-pad the data to length N if necessary and return an empty array array if the number of elements
// in the input array is not a power of 2
dim M as integer = Ubound(x) + 1
if N > M then
if not IsPowerof2(N) then
dim c() as Complex
return c
else
x = ZeroPad(x, N)
end if
else
if not IsPowerOf2(M) then
dim c() as Complex
return c
end if
end if
// Calculate the FFT
return FFT_int(x)
End Function
Function FFT(x() as double, N as integer = -1) As Complex()
// FFT using real numbers as input
//Calculate the smallest power of 2 greater than the upper bound of x
if n = -1 then
dim powerof2 as integer = 2
dim ub as integer = UBound(x)
while powerof2 < ub
powerof2 = powerof2 * 2
wend
n = powerof2
end if
// Convert input array to Complex
dim M as integer = UBound(x)
dim c() as Complex
for k as integer = 0 to M
c.Append new Complex(x(k),0)
next
return FFT(c, N)
End Function
Private Function FFT_int(x() as complex) As Complex()
// Radix-2 Decimation in Time FFT algorithm (Cooley-Tukey)
// Source: http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm
//#pragma DisableBackgroundTasks
// If the input array only contains 1 element then we've reached the end of the recursion
dim N as integer = UBound(x) ' number of elements - 1 in the input array
if N = 0 then
return x
end if
// Split the input array in to Even and Odd, each with half the elements
dim Even() as Complex
dim Odd() as Complex
dim N2 as integer = (N+1) \ 2 - 1
redim Even(N2)
redim Odd(N2)
for k as integer = 0 to N2
Odd(k) = x(2*k)
Even(k) = x(2*k + 1)
next
// Recursively calculate the FFT for Even and Odd
dim Even_() as Complex = FFT_int(Even)
dim Odd_() as Complex = FFT_int(Odd)
// Multiply elements of Odd_ with the Twiddle-Factors e^(-2 * pi * j / (N+1) * k)
dim j as Complex = new Complex(0,1)
dim W as Complex = -2 * pi * j / (N+1)
for k as integer = 0 to N2
Odd_(k) = Odd_(k) * Complex(W * k).Exp
next
// Reconstruct FFT from Even_ and Odd_
dim X_() as Complex // Output Array
redim X_(N)
for k as integer = 0 to N2
X_(k) = Even_(k) + Odd_(k)
X_(k + N2 + 1) = Even_(k) - Odd_(k)
next
Return X_
End Function
Private Function IsPowerOf2(N as integer) As boolean
// if a number n is a power of 2, only one bit is set, all the others are cleared.
// In that case (n - 1) is the bitwise NOT of n. I.e. if and only if x is a power of 2, n AND (n-1) must be 0
if (N and (N-1)) = 0 then return true
Return false
End Function
Function ZeroPad(c() as Complex, N as integer) As Complex()
// extends the vector c() with zeros to the length of N
dim M as integer = UBound(c) + 1
for k as integer = M to N - 1
c.Append new Complex
next
Return c
End Function
Function ZeroPad(x() as double, N as integer) As double()
// extends the vector x() with zeros to the length of N
dim M as integer = UBound(x) + 1
for k as integer = M to N - 1
x.Append 0
next
return x
End Function
End Module
Class Complex
Const Pi = 3.141592653589793238462643383279502884197169399375105820974944592
Function Abs() As double
// Absolute Value of a complex number
// abs(z) = sqrt(norm(z))
return sqrt(me.Norm)
End Function
Sub Constructor()
mImag = 0
mReal = 0
End Sub
Sub Constructor(Real as double, Imag as double)
mImag = Imag
mReal = Real
End Sub
Function Exp() As complex
// complex exponential
// exp(x + i*y) = exp(x) * ( cos(y) + i * sin(y) )
dim cp as new Complex
cp.Real = exp(mReal) * cos(mImag)
cp.Imag = exp(mReal) * sin(mImag)
return cp
End Function
Function Imag() As double
Return mImag
End Function
Sub Imag(assigns im as double)
mImag = im
End Sub
Function Norm() As double
// Square of the "length" of a complex number
// norm(x + i*y) = x*x + y*y
return mReal^2 + mImag^2
End Function
Function Operator_Add(c as complex) As complex
// Sum of two Complex numbers
// (a + i*b) + (c + i*d) = ((a+c) + i*(b+d))
dim cp as new Complex
cp.Real = mReal + c.Real
cp.Imag = mImag + c.Imag
Return cp
End Function
Function Operator_Add(d as double) As complex
// Sum of a complex number and a real number
// (a + i*b) + d = ((a+d) + i*b)
dim cp as new Complex
cp.Real = mReal + d
cp.Imag = mImag
Return cp
End Function
Function Operator_Divide(c as complex) As complex
// Division of two Complex numbers
// (a + i*b) / (c + i*d) = ( (a*c) + (b*d) + i*((b*c) - (a*d)) ) / norm(c + i*d)
dim cp as new Complex
cp.Real = (mReal * c.Real + mImag * c.Imag) / (c.Real^2 + c.Imag^2)
cp.Imag = (mImag * c.Real - mReal * c.Imag) / (c.Real^2 + c.Imag^2)
Return cp
End Function
Function Operator_Divide(d as double) As complex
// Product of a complex number and a real number
// (a + i*b) / d = ( (a/d) + i*(b/d) )
dim cp as new Complex
cp.Real = mReal / d
cp.Imag = mImag / d
Return cp
End Function
Function Operator_Multiply(c as complex) As complex
// Product of two Complex numbers
// (a + i*b) * (c + i*d) = ( (a*c) - (b*d) + i*((a*d) + (b*c)) )
dim cp as new Complex
cp.Real = mReal * c.Real - mImag * c.Imag
cp.Imag = mReal * c.Imag + mImag * c.Real
Return cp
End Function
Function Operator_Multiply(d as double) As complex
// Product of a complex number and a real number
// (a + i*b) * d = ( (a*d) + i*(b*d) )
dim cp as new Complex
cp.Real = mReal * d
cp.Imag = mImag * d
Return cp
End Function
Function Operator_MultiplyRight(d as double) As complex
// Product of a complex number and a real number
// (a + i*b) * d = ( (a*d) + i*(b*d) )
dim cp as new Complex
cp.Real = mReal * d
cp.Imag = mImag * d
Return cp
End Function
Function Operator_Subtract(c as complex) As complex
// Difference of two Complex numbers
// (a + i*b) - (c + i*d) = ((a-c) + i*(b-d))
dim cp as new Complex
cp.Real = mReal - c.Real
cp.Imag = mImag - c.Imag
Return cp
End Function
Function Operator_Subtract(d as double) As complex
// Difference of a complex number and a real number
// (a + i*b) - d = ((a-d) + i*b)
dim cp as new Complex
cp.Real = mReal - d
cp.Imag = mImag
Return cp
End Function
Function Real() As double
Return mReal
End Function
Sub Real(assigns re as double)
mReal = re
End Sub
Property Private mImag As Double
Property Private mReal As Double
End Class
End Project
The items on this page are in the following plugins: MBS DataTypes Plugin.