On May 8, 9:07 pm, Jerry Coffin <jcof...@[EMAIL PROTECTED]
> wrote:
> Since you're doing an FFT, I'd guess you don't care about the
> possibility of N being odd.
(There are plenty of FFT algorithms that work for odd N, although it's
true that FFT users often restrict themselves to the even case, and
most implementations are optimized primarily for sizes with many
factors of 2.)
I would say that, if the original poster really cares about
performance, he should just arrange his code so that he doesn't need
the swap/****ft -- he should work with the FFT output in the natural
DFT order, with the origin at the left of the array, rather than
trying to ****ft the origin to the center.
****fting the origin to the center (like in Matlab's fft****ft function)
is just a convenience for visualization, and is not necessary for any
high-performance computational application of the FFT. (If you are
just plotting the data and want to ****ft it to make a prettier plot, I
would be surprised if the time to ****ft it is a serious performance
bottleneck.)
Steven
PS. For even N, the fastest way to ****ft by N/2 is almost certainly
just a loop of N/2 swaps in-place as another poster pointed out. For
odd N, or for an arbitrary cyclic ****ft of the array, in the past
we've found that the fastest scheme is to do two in-place p***** over
the array: one to reverse the order, and one to un-reverse the two
segments before and after the ****ft.
|
