Thread Subject: FFT Time

Hi All,
I knew that FFT takes less time when number of samples in a time series are 2^n. I gave a test using following code and found that the time to compute FFT of 1364 values is less than the 1024 values. Can any one explain why this is so?
Regards,
Ravi

I used following code to calculate the time:
f1=rand(1364,1);
f2=rand(1023,1);
%%
tic
ff1=fft(f1);
toc
%%
tic
ff2=fft(f2);
toc

"Ravi " <ravi.ngri@gmail.com> wrote in message <h3darn$suh$1@fred.mathworks.com>...


> f2=rand(1023,1); <- You seem to have a finger larger than the keyboard key size.

Bruno

Ravi wrote:
> Hi All, I knew that FFT takes less time when number of samples in a
> time
series are 2^n. I gave a test using following code and found that the
time to compute FFT of 1364 values is less than the 1024 values. Can any
one explain why this is so?
> Regards, > Ravi
>
> I used following code to calculate the time:
> f1=rand(1364,1);
> f2=rand(1023,1);
> %%
> tic
> ff1=fft(f1);
> toc
> %%
> tic
> ff2=fft(f2);
> toc

Besides Bruno's observation, before you assign too much into the
differences run this enough times to get a feeling for the variability
in timings.

--

On Jul 12, 2:43 pm, "Ravi " <ravi.n...@gmail.com> wrote:
> Hi All,
> I knew that FFT takes less time when number of samples in a time series are 2^n. I gave a test using following code and found that the time to compute FFT of 1364 values is less than the 1024 values. Can any one explain why this is so?
> Regards,
> Ravi
>
> I used following code to calculate the time:
> f1=rand(1364,1);
> f2=rand(1023,1);
> %%
> tic
> ff1=fft(f1);
> toc
> %%
> tic
> ff2=fft(f2);
> toc

f2=rand(1024,1);

tic
for i = 1:1000
    ff1=fft(f1);
end
toc

tic
for i = 1:1000
    ff2=fft(f2);
end
toc

Hope this helps.

Greg

Note that the first FFT of a given size requires some extra time to
set up the algorithm, trig. tables, etcetera. So, it is probably more
informative to measure the marginal time to perform FFTs after the
first one, e.g.

ff1 = fft(f1)
tic
for i = 1:1000
  ff1 = fft(f1)
end
toc

Regards,
Steven G. Johnson

On Jul 12, 2:43 pm, "Ravi " <ravi.n...@gmail.com> wrote:
> I knew thatFFTtakes less time when number of samples in a time series are 2^n. I gave a test using following code and found that the time to computeFFTof 1364 values is less than the 1024 values. Can any one explain why this is so?

On another note, I should mention that the correct statement is no
longer "2^n sizes are more efficient" but rather "sizes with small
prime factors (<= 7, and ideally several factors of 2) are most
efficient."

However, 1364 has factors of 11 and 31, so it should certainly be much
slower than 1024.

(On my 2.8GHz Intel Core 2 with FFTW 3.2 from C (gcc), a size-1024
complex-data transform takes about 7.4 microseconds, a size-1364
transform takes 44 microseconds, and a size-768 transform takes 5.33
microseconds. Although Matlab uses FFTW, it will be somewhat slower
than calling FFTW directly from C for a variety of reasons.)

Regards,
Steven G. Johnson

Thanks Steven for your several constructive comments and examples.
1023 was my mistake, It so happen that just to test less than radix 2
(ie. 1024) I changed it to 1023 and while posting I forgot to correct
it, my apologies for that.

The anomalous result was due to first time run as rightly pointed out
by Steven, in subsequent runs it took less time.
Thanks to all for their constructive comments.
Ravi



On Jul 14, 1:15 am, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
> On Jul 12, 2:43 pm, "Ravi " <ravi.n...@gmail.com> wrote:
>
> > I knew thatFFTtakes less time when number of samples in a time series are 2^n. I gave a test using following code and found that the time to computeFFTof 1364 values is less than the 1024 values. Can any one explain why this is so?
>
> On another note, I should mention that the correct statement is no
> longer "2^n sizes are more efficient" but rather "sizes with small
> prime factors (<= 7, and ideally several factors of 2) are most
> efficient."
>
> However, 1364 has factors of 11 and 31, so it should certainly be much
> slower than 1024.
>
> (On my 2.8GHz Intel Core 2 with FFTW 3.2 from C (gcc), a size-1024
> complex-data transform takes about 7.4 microseconds, a size-1364
> transform takes 44 microseconds, and a size-768 transform takes 5.33
> microseconds.  Although Matlab uses FFTW, it will be somewhat slower
> than calling FFTW directly from C for a variety of reasons.)
>
> Regards,
> Steven G. Johnson

On Jul 14, 5:50 am, Ravi Srivastava <ravi.n...@gmail.com> wrote:
> Thanks Steven for your several constructive comments and examples.
> 1023 was my mistake, It so happen that just to test less than radix 2
> (ie. 1024)  I changed it to 1023 and while posting I forgot to correct
> it, my apologies for that.

Note that Matlab's fft (FFTW) does not typically use a radix-2
algorithm for 1024. (It probably uses radix-32, breaking it down into
32 sub-transforms of size 32, each of which is handled by a hard-coded
size-32 FFT.)

Steven