One-line FFT, nice!

[Paulo Pinto]

On Sunday, 9 September 2012 at 06:20:14 UTC, Mehrdad wrote:
> On Saturday, 8 September 2012 at 23:58:36 UTC, Walter Bright
> wrote:
>> On 9/8/2012 3:56 PM, 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!
>>
>> Awesome! Thanks for figuring this out. Any chance you can 
>> write up a brief article on this, so we can post a link on 
>> reddit?
>
> Haha... I wish, but I don't have a blog or anything like that.
> Currently I'm working on schoolwork though so I'm not sure I'd
> get to this in time. :\
>
> If someone else wants to do it though, feel free to!
>
> Also, obligatory mention, sorry I didn't mention this earlier --
> Bearophile is right on, I got the original code from
> http://rosettacode.org/wiki/FFT (Python) and then I played 
> around
> with it to make it a one-liner.
> Credits go there for the original code, not me. :)

If you provide me the text, I can publish it on my web site.

--
Paulo