module ftu_mod

implicit none
contains

subroutine ftu(signi, nx, cx )
	integer nx, i, j, k, m, istep, pad2
	real    signi, scale, arg
	complex cx(nx), cmplx, cw, cdel, ct 

	if( nx /= pad2(nx)) call erexit('ftu: nx not a power of 2')	
	scale = 1. / sqrt( 1.*nx)
	do i= 1, nx
        	cx(i) = cx(i) * scale
		j = 1;  k = 1
	end do
	do i= 1, nx 
        	if (i<=j)then; ct = cx(j); cx(j) = cx(i); cx(i) = ct ;endif
	        m = nx/2
        	do while (j>m .and. m>1)
			j = j-m; m = m/2 
		        j = j+m
		end do
        enddo
	do j=1,nx*nx
	        istep = 2*k;   cw = 1.;   arg = signi*3.14159265/k
        	cdel = cmplx( cos(arg), sin(arg))
	        do m= 1, k 
        	        do i= m, nx, istep
                	        ct=cw*cx(i+k);  cx(i+k)=cx(i)-ct;  cx(i)=cx(i)+ct 
			end do
        	        cw = cw * cdel
	        end do
        	k=istep
        	if(k>=nx) exit
	enddo
return; 
end subroutine



integer function pad2(n)
	integer n
	pad2 = 1
	do while( pad2 < n )
		pad2 = pad2 * 2 
	enddo
	return; 
end function

end module