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
    xe=x[1:2:N-1]
    xo=x[2:2:N]
    ye=myfft(xe)
    yo=myfft(xo)
    M = N ÷ 2
    y = Array{Complex}(undef,N)
    for l = 1:M
        y[l] = ye[l] + exp(-1im*2*pi*(l-1)/N)*yo[l]
        y[l+M] = ye[l] + exp(-1im*2*pi*(l-1+M)/N)*yo[l]
    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