extra/math/fft/fft.factor

   1 ! Fast Fourier Transform, copyright (C) 2007 Hans Schmid
   2 ! http://dressguardmeister.blogspot.com/2007/01/fft.html
   3 USING: arrays sequences math math.vectors math.constants
   4 math.functions kernel splitting columns ;
   5 IN: math.fft
   6
   7 : n^v ( n v -- w ) [ ^ ] with map ;
   8 : even ( seq -- seq ) 2 group 0 <column> ;
   9 : odd ( seq -- seq ) 2 group 1 <column> ;
  10 DEFER: fft
  11 : two ( seq -- seq ) fft 2 v/n dup append ;
  12 : omega ( n -- n ) recip -2 pi i* * * exp ;
  13 : twiddle ( seq -- seq ) dup length dup omega swap n^v v* ;
  14 : (fft) ( seq -- seq ) dup odd two twiddle swap even two v+ ;
  15 : fft ( seq -- seq ) dup length 1 = [ (fft) ] unless ;