This is a Fast Fourier Transform program.

It expects an array of the numbers to transform to be on the second level of
the stack and a number that says what to do on level 1.

The number is as follows:
	-1	normal transform
	1	inverse transform

The transformed array is returned on level 1.  It can also be found in the
global variable 'a'

This is just the first version of this program.  People please help my
improve this program and send me any changes.

FFT
<< 
   SWAP DUP SIZE (0,0) CON + 'a' STO 		;convert a to complex and STO
   a SIZE LIST-> DROP LN 2 LN / .5 + FLOOR	;find m ( 2^m=number )
   -> sign m <<
     2 m ^ 		; 2^m
     DUP 2 /		; 2^(m-1)
     OVER 1 -		; 2^m-1
     1
     0
     -> n nv2 nm1 j k <<
       1 nm1 FOR i
	 IF i j < THEN 
	   'a' j GET 		;swap( a(i),a(j) )
	   'a' i GET
	   'a' j ROT PUT
	   'a' i ROT PUT
	 END
	 nv2 'k' STO
	 WHILE k j < REPEAT
	   j k - 'j' STO
	   k 2 / 'k' STO
	 END
	 j k + 'j' STO
       NEXT
       1 m FOR l
	 2 l ^		;2^l
	 DUP 2 /	;2^(l-1)
	 1
	 [PI] sign * 2 l ^ 2 / / (0,1) * EXP
	 0
	 -> le le1 u w ip <<
	   1 le1 FOR j
	     j n FOR i
	       i le1 + 'ip' STO
	       'a' ip GET u *		;t=a(ip)*u
	       'a' i GET
	       OVER - 'a' ip ROT PUT	;a(ip)=a(i)-t
	       'a' i GET +
	       'a' i ROT PUT		;a(i)=a(i)+t
	     le STEP
	     u w * 'u' STO
	   NEXT
	 >>
       NEXT
       IF sign 0 > THEN
	 'a' n STO/
       END
       a
     >>
   >>
 >>

If you didn't guess from the program this is a ported FORTRAN program.

_______________________________________________________________________________
Wayne Scott             |  INTERNET:   wscott@en.ecn.purdue.edu
Electrical Engineering  |  BITNET:     wscott%ea.ecn.purdue.edu@purccvm
Purdue University       |  UUCP:      {purdue, pur-ee}!en.ecn.purdue.edu!wscott
