1 ! Copyright (c) 2007 Hans Schmid.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: columns grouping kernel math math.constants math.functions math.vectors
5 IN: math.transforms.fft
7 ! Fast Fourier Transform
11 : n^v ( n v -- w ) [ ^ ] with map ;
14 recip -2 pi i* * * exp ;
16 : twiddle ( seq -- seq )
17 dup length [ omega ] [ n^v ] bi v* ;
24 fft 2 v/n dup append ;
28 : even ( seq -- seq ) 2 group 0 <column> ;
29 : odd ( seq -- seq ) 2 group 1 <column> ;
31 : (fft) ( seq -- seq )
32 [ odd two twiddle ] [ even two ] bi v+ ;
37 dup length 1 = [ (fft) ] unless ;