www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - One-line FFT, nice!

reply "Mehrdad" <wfunction hotmail.com> writes:
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!
Sep 08 2012
next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
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?
Sep 08 2012
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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?
Sep 08 2012
parent Timon Gehr <timon.gehr gmx.ch> writes:
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.
Sep 08 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Sep 08 2012
prev sibling next sibling parent Brad Roberts <braddr puremagic.com> writes:
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?
Sep 08 2012
prev sibling next sibling parent "Mehrdad" <wfunction hotmail.com> writes:
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. :)
Sep 08 2012
prev sibling next sibling parent "Mehrdad" <wfunction hotmail.com> writes:
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
Sep 08 2012
prev sibling next sibling parent Manu <turkeyman gmail.com> writes:
--047d7bd75162c65dcc04c97ec09b
Content-Type: text/plain; charset=UTF-8

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?

--047d7bd75162c65dcc04c97ec09b
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div class=3D"gmail_quote">On 9 September 2012 01:56, Mehrdad <span dir=3D"=
ltr">&lt;<a href=3D"mailto:wfunction hotmail.com" target=3D"_blank">wfuncti=
on hotmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" s=
tyle=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I was pretty excited to figure out that a one-liner FFT is<br>
possible in D!<br>
creal[] dft(creal[] v) { return v.length &gt; 1 ? (p =3D&gt; chain(map!(q<b=
r>
=3D&gt; q[0] + q[1])(p), map!(q =3D&gt; q[0] -<br>
q[1])(p)))(zip(dft(v.stride(2)<u></u>.array()), map!(p =3D&gt; p[1] *<br>
expi(p[0] * -2 * PI / v.length))(zip(iota(v.length / 2),<br>
dft(v.drop(1).stride(2).array(<u></u>)))))).array() : v; }<br>
<br>
Of course, the Python version is still shorter:<br>
def dft(v): return (lambda e, o: map(add, e, o) + map(sub, e,<br>
o))(dft(v[0::2]), [o * rect(1, k * -2 * pi / len(v)) for k, o in<br>
enumerate(dft(v[1::2]))]) if len(v) &gt; 1 else v<br>
<br>
but it&#39;s still cool (barring the unreadability, haha).<br>
Yay D!<br>
</blockquote></div><br><div>Very curious to know how this performs. Since i=
t&#39;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 optimi=
sing this?</div>

--047d7bd75162c65dcc04c97ec09b--
Sep 12 2012
prev sibling next sibling parent "Paulo Pinto" <pjmlp progtools.org> writes:
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
Sep 12 2012
prev sibling parent "jerro" <a a.com> writes:
 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?



It is computing sine and cosine in the inner loop, so the
performance can not be good, no matter how well the compiler
optimizes it.
Sep 12 2012