Example: /DataTypes/FFT

Online Documentation   -   Statistics   -   FAQ   -   Plugin Parts (All, Dependencies)   -   Class hierarchy

New in Version 22.2 22.3 22.4 22.5 23.0 23.1 23.2 23.3 23.4 23.5 24.0 24.1

The list of the   topics,   classes,   interfaces,   controls,   modules,   global methods by category,   global methods by name,   screenshots,   licenses   and   examples.

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.


💬 Ask a question or report a problem