user
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.
assistant
(formerly Perl 6)

**Works with**: rakudo 2022-07

|  |
| --- |
| This example is **in need of improvement:**  Not numerically accurate |

```
sub fft {
    return @_ if @_ == 1;
    my @evn = fft( @_[0, 2 ... *] );
    my @odd = fft( @_[1, 3 ... *] ) Z*
    map &cis, (0, -tau / @_ ... *);
    return flat @evn »+« @odd, @evn »-« @odd;
}

.say for fft <1 1 1 1 0 0 0 0>;

```

Output:

```
4+0i
1-2.414213562373095i
0+0i
1-0.4142135623730949i
0+0i
0.9999999999999999+0.4142135623730949i
0+0i
0.9999999999999997+2.414213562373095i

```

For the fun of it, here is a purely functional version:

```
sub fft {
    @_ == 1 ?? @_ !!
    fft(@_[0,2...*]) «+«
    fft(@_[1,3...*]) «*« map &cis, (0,-τ/@_...^-τ)
}

```