FFT is not that Fast !

The Fast Fourier Transform (FFT) algorithm takes a list of numbers of dimension N and constructs the DFT. Mathematica has a built in function that uses it in order to calculate the DFT of a list i.e. Fourier[list].

num=10;
list=Table[i,{i,0,num}]
Fourier[list]

(* Lets write a code to see how long this takes as a function of N (num) the length
in the number of integers *)

timer[n_]:=Module[{t,list},list=Table[i,{i,0,2^n}];
t=Timing[Fourier[list]];{N[Log[2^n]],Log[t[[1]]]}]

timer[14]

table=Table[timer[i],{i,1,23}]

line=Fit[table,{1,x},x]

Show[ListPlot[table,PlotStyle->{Red,PointSize->0.025}],Plot[line,{x,1,20}],AxesLabel->{Log[2^n],Log[t]},PlotRange->All]

Thus as the length in the number of digits in the string grows, the  logarithm of the time it takes
for FFT to get the DFT  seems to scale linearly with the Logarithm of the size of the number.  Again, this
implies a non-polynomial scaling of t as a function of n.  Thus if we wish to find the period of a function
Mod[ (x^r),N]  using the classical FFT, as r gets large this becomes prohibitive.