function myfft(x) N=length(x) if N == 1 return x end if N % 2 == 1 println("N = ",N," was not even!") throw(ArgumentError) end ye=myfft(x[1:2:N-1]) yo=myfft(x[2:2:N]) M = N รท 2 y = Array{Complex}(undef,N) for l = 1:M z0 = ye[l] z1 = exp(-1im*2*pi*(l-1)/N)*yo[l] y[l] = z0 + z1 y[l+M] = z0 - z1 end return y end for n=2:18 N=2^n x=rand(N) println("N=",N) @time xhat=myfft(x) # println("x=",x) # println("xhat=",xhat) end