Platforms to show: All Mac Windows Linux Cross-Platform

/DataTypes/FFT


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.


The biggest plugin in space...