Task

Calculate the   FFT   (Fast Fourier Transform)   of an input sequence.

The most general case allows for complex numbers at the input
and results in a sequence of equal length, again of complex numbers.
If you need to restrict yourself to real numbers, the output should
be the magnitude   (i.e.:   sqrt(re2 + im2))   of the complex result.

The classic version is the recursive Cooley–Tukey FFT. Wikipedia has pseudo-code for that.
Further optimizations are possible but not required.




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
}
 