Thread overview | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
September 08, 2012 One-line FFT, nice! | ||||
---|---|---|---|---|
| ||||
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! |
September 08, 2012 Re: One-line FFT, nice! | ||||
---|---|---|---|---|
| ||||
Posted in reply to Mehrdad | 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?
|
September 09, 2012 Re: One-line FFT, nice! | ||||
---|---|---|---|---|
| ||||
Posted in reply to Mehrdad | 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?
|
September 09, 2012 Re: One-line FFT, nice! | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On 09/09/2012 02:57 AM, Timon Gehr wrote:
> 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?
Works correctly in 32 bit mode. 64 bit code gen bug.
|
September 09, 2012 Re: One-line FFT, nice! | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | Walter Bright: > 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? See also: http://rosettacode.org/wiki/FFT#D Bye, bearophile |
September 09, 2012 Re: One-line FFT, nice! | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On 9/8/2012 6:01 PM, Timon Gehr wrote:
> On 09/09/2012 02:57 AM, Timon Gehr wrote:
>> 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?
>
> Works correctly in 32 bit mode. 64 bit code gen bug.
Bug number?
|
September 09, 2012 Re: One-line FFT, nice! | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | 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. :) |
September 09, 2012 Re: One-line FFT, nice! | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On Sunday, 9 September 2012 at 01:01:00 UTC, Timon Gehr wrote:
> Works correctly in 32 bit mode. 64 bit code gen bug.
Hehe, glad it was helpful. :D
|
September 12, 2012 Re: One-line FFT, nice! | ||||
---|---|---|---|---|
| ||||
Posted in reply to Mehrdad Attachments:
| On 9 September 2012 01:56, Mehrdad <wfunction@hotmail.com> 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!
>
Very curious to know how this performs. Since it's making use of lots of templates from the standard library, how much do they influence efficiency? How well does the compiler do its job optimising this?
|
September 12, 2012 Re: One-line FFT, nice! | ||||
---|---|---|---|---|
| ||||
Posted in reply to Mehrdad | 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
|
Copyright © 1999-2021 by the D Language Foundation