One-line FFT, nice!

[Timon Gehr]

On 09/09/2012 12:56 AM, Mehrdad wrote:
> I was pretty excited to figure out that a one-liner FFT is
> possible in D!
> creal[] dft(creal[] v) { return v.length > 1 ? (p => chain(map!(q
> => q[0] + q[1])(p), map!(q => q[0] -
> q[1])(p)))(zip(dft(v.stride(2).array()), map!(p => p[1] *
> expi(p[0] * -2 * PI / v.length))(zip(iota(v.length / 2),
> dft(v.drop(1).stride(2).array()))))).array() : v; }
>
> Of course, the Python version is still shorter:
> def dft(v): return (lambda e, o: map(add, e, o) + map(sub, e,
> o))(dft(v[0::2]), [o * rect(1, k * -2 * pi / len(v)) for k, o in
> enumerate(dft(v[1::2]))]) if len(v) > 1 else v
>
> but it's still cool (barring the unreadability, haha).
> Yay D!

I usually get NaNs. Are you sure this is correct?