Fast Fourier transform: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 2,722: | Line 2,722: | ||
0.000000000000+0.000000000000I |
0.000000000000+0.000000000000I |
||
0.999999999999+2.414213562373I</pre> |
0.999999999999+2.414213562373I</pre> |
||
=={{header|PowerShell}}== |
|||
<lang PowerShell>Function FFT($Arr){ |
|||
$Len = $Arr.Count |
|||
If($Len -le 1){Return $Arr} |
|||
$Len_Over_2 = [Math]::Floor(($Len/2)) |
|||
$Output = New-Object System.Numerics.Complex[] $Len |
|||
$EvenArr = @() |
|||
$OddArr = @() |
|||
For($i = 0; $i -lt $Len; $i++){ |
|||
If($i % 2){ |
|||
$OddArr+=$Arr[$i] |
|||
}Else{ |
|||
$EvenArr+=$Arr[$i] |
|||
} |
|||
} |
|||
$Even = FFT($EvenArr) |
|||
$Odd = FFT($OddArr) |
|||
For($i = 0; $i -lt $Len_Over_2; $i++){ |
|||
$Twiddle = [System.Numerics.Complex]::Exp([System.Numerics.Complex]::ImaginaryOne*[Math]::Pi*($i*-2/$Len))*$Odd[$i] |
|||
$Output[$i] = $Even[$i] + $Twiddle |
|||
$Output[$i+$Len_Over_2] = $Even[$i] - $Twiddle |
|||
} |
|||
Return $Output |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre>Real Imaginary Magnitude Phase |
|||
---- --------- --------- ----- |
|||
4 0 4 0 |
|||
1 -2.41421356237309 2.61312592975275 -1.17809724509617 |
|||
0 0 0 0 |
|||
1 -0.414213562373095 1.08239220029239 -0.392699081698724 |
|||
0 0 0 0 |
|||
1 0.414213562373095 1.08239220029239 0.392699081698724 |
|||
0 0 0 0 |
|||
1 2.41421356237309 2.61312592975275 1.17809724509617</pre> |
|||
=={{header|Prolog}}== |
=={{header|Prolog}}== |