extra/math/transforms/fft/fft.factor

   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
   4     sequences ;
   5 IN: math.transforms.fft
   6
   7 ! Fast Fourier Transform
   8
   9 <PRIVATE
  10
  11 : n^v ( n v -- w ) [ ^ ] with map ;
  12
  13 : omega ( n -- n' )
  14     recip -2 pi i* * * exp ;
  15
  16 : twiddle ( seq -- seq' )
  17     dup length [ omega ] [ n^v ] bi v* ;
  18
  19 PRIVATE>
  20
  21 DEFER: fft
  22
  23 : two ( seq -- seq' )
  24     fft 2 v/n dup append ;
  25
  26 <PRIVATE
  27
  28 : even ( seq -- seq' ) 2 group 0 <column> ;
  29 : odd ( seq -- seq' ) 2 group 1 <column> ;
  30
  31 : (fft) ( seq -- seq' )
  32     [ odd two twiddle ] [ even two ] bi v+ ;
  33
  34 PRIVATE>
  35
  36 : fft ( seq -- seq' )
  37     dup length 1 = [ (fft) ] unless ;
  38