Fast Fourier transform: Difference between revisions
m
→Recursive
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→Recursive) |
||
| (8 intermediate revisions by 5 users not shown) | |||
Line 229:
FOR I% = 0 TO 7
READ in{(I%)}.r#
out{(I%)}.r# = in{(I%)}.r#
PRINT in{(I%)}.r# "," in{(I%)}.i#
NEXT
Line 2,708 ⟶ 2,709:
ucomplex;
{$WARN 6058 off : Call to subroutine "$1" marked as inline is not inlined}
(*) Use for variants and ucomplex (*)
Line 3,645 ⟶ 3,648:
=={{header|Raku}}==
(formerly Perl 6)
{{Works with|rakudo
{{improve|raku|Not numerically accurate}}
<syntaxhighlight lang="raku" line>sub fft {
return @_ if @_ == 1;
Line 3,653 ⟶ 3,657:
return flat @evn »+« @odd, @evn »-« @odd;
}
.say for fft <1 1 1 1 0 0 0 0>;</syntaxhighlight>
{{out}}
<pre>4+0i
0+0i
1-0.4142135623730949i
▲1-0.414213562373095i
0+0i
0.9999999999999999+0.4142135623730949i
1+0.414213562373095i▼
0+0i
</pre>
For the fun of it, here is a purely functional version:
Line 3,673 ⟶ 3,678:
}</syntaxhighlight>
<!-- Not really helping now
This particular version is numerically inaccurate though, because of the pi approximation. It is possible to fix it with the 'cisPi' function available in the TrigPi module:
Line 3,681 ⟶ 3,687:
fft(@_[1,3...*]) «*« map &cisPi, (0,-2/@_...^-2)
}</syntaxhighlight>
-->
=={{header|REXX}}==
Line 4,606 ⟶ 4,613:
1.000e+00+2.414e+00j>)</pre>
=={{header|
{{works with|VBA}}
{{trans|BBC_BASIC}}
Written and tested in Microsoft Visual Basic for Applications 7.1 under Office 365 Excel; but is probably useable under any recent version of VBA.
<syntaxhighlight lang="vba">Option Base 0
Private Type Complex
re As Double
im As Double
End Type
Private Function cmul(c1 As Complex, c2 As Complex) As Complex
Dim ret As Complex
ret.re = c1.re * c2.re - c1.im * c2.im
ret.im = c1.re * c2.im + c1.im * c2.re
cmul = ret
End Function
Public Sub FFT(buf() As Complex, out() As Complex, begin As Integer, step As Integer, N As Integer)
Dim i As Integer, t As Complex, c As Complex, v As Complex
If step < N Then
FFT out, buf, begin, 2 * step, N
FFT out, buf, begin + step, 2 * step, N
i = 0
While i < N
t.re = Cos(-WorksheetFunction.Pi() * i / N)
t.im = Sin(-WorksheetFunction.Pi() * i / N)
c = cmul(t, out(begin + i + step))
buf(begin + (i \ 2)).re = out(begin + i).re + c.re
buf(begin + (i \ 2)).im = out(begin + i).im + c.im
buf(begin + ((i + N) \ 2)).re = out(begin + i).re - c.re
buf(begin + ((i + N) \ 2)).im = out(begin + i).im - c.im
i = i + 2 * step
Wend
End If
End Sub
' --- test routines:
Private Sub show(r As Long, txt As String, buf() As Complex)
Dim i As Integer
r = r + 1
Cells(r, 1) = txt
For i = LBound(buf) To UBound(buf)
r = r + 1
Cells(r, 1) = buf(i).re: Cells(r, 2) = buf(i).im
Next
End Sub
Sub testFFT()
Dim buf(7) As Complex, out(7) As Complex
Dim r As Long, i As Integer
buf(0).re = 1: buf(1).re = 1: buf(2).re = 1: buf(3).re = 1
r = 0
show r, "Input (real, imag):", buf
FFT out, buf, 0, 1, 8
r = r + 1
show r, "Output (real, imag):", out
End Sub
</syntaxhighlight>
{{out}}
<pre>Input (real, imag):
1 0
1 0
1 0
1 0
0 0
0 0
0 0
0 0
Output (real, imag):
4 0
1 -2.414213562
0 0
1 -0.414213562
0 0
1 0.414213562
0 0
1 2.414213562</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">import math.complex
import math
fn ditfft2(x []f64, mut y []Complex, n int, s int) {
Line 4,653 ⟶ 4,743:
{{libheader|Wren-complex}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
var ditfft2 // recursive
| |||