optimize this Shifting code ?

[Matthias Pospiech]

In FFT one usually needs to shift/cycle the values in an array.
Typically the entries are shifted in the way:
012 345 to 345 012

The following code does this, but I wonder if there are possibilites to
optimize it? It is very generall, but the shifting with the delimiter in
the middle is the only one that I need.

// *********************************
// Cycle changes 012 345 to 345 012
// *********************************
void QFFTW::Cycle(complex<double> *A1,long N)
{
Cycle(A1,N,N/2);
}


void QFFTW::Cycle(complex<double> *A1,long N,long del)
{
long i;
complex<double> *D;

D=new complex<double>[N];

if (del>=N) del-=N;
if (del<=-N) del+=N;

if(del>0 && del<N)
{
for (i=N-del;i<N;i++) D[i-N+del]=A1;
for (i=N-1;i>=del;i--) A1=A1[i-del];
for (i=0;i<del;i++) A1=D;
}
else if(del<0 && del > -N)
{
del=-del;
for (i=0;i<del;i++) D=A1;
for (i=0;i<N-del;i++) A1=A1[i+del];
for (i=N-del;i<N;i++) A1=D[i-N+del];
}
delete [] D;
}

 

[lunar_lty]

The following code does this, but I wonder if there are possibilites to

optimize it? It is very generall, but the shifting with the delimiter in
the middle is the only one that I need.

// *********************************
// Cycle changes 012 345 to 345 012
// *********************************

As you said, the shifting with the delimiter in the middle is the one
you need.
That means you only need to do is to swap them.
Ex: the original Cycle: 012 345 .
Now swap(0,3),(1,4), (2,5), result is Cycle: 345 012

 

[Jerry Coffin]

In FFT one usually needs to shift/cycle the values in an array.
Typically the entries are shifted in the way:
012 345 to 345 012

The following code does this, but I wonder if there are possibilites to
optimize it? It is very generall, but the shifting with the delimiter in
the middle is the only one that I need.

// *********************************
// Cycle changes 012 345 to 345 012
// *********************************
void QFFTW::Cycle(complex<double> *A1,long N)
{
Cycle(A1,N,N/2);
}

If I understand your requirements correctly, std::swap_ranges should do
the job quite easily:

void QFFTW::Cycle(complex<double> *A1, long N) {
complex<double> *mid = A1+N/2;
std::swap_ranges(A1, mid, mid);
}

Since you're doing an FFT, I'd guess you don't care about the
possibility of N being odd.

 

[Steven G. Johnson]

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/shift -- 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 shift the origin to the center.

Shifting the origin to the center (like in Matlab's fftshift 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 shift it to make a prettier plot, I
would be surprised if the time to shift it is a serious performance
bottleneck.)

Steven

PS. For even N, the fastest way to shift 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 shift of the array, in the past
we've found that the fastest scheme is to do two in-place passes over
the array: one to reverse the order, and one to un-reverse the two
segments before and after the shift.

 

[Jerry Coffin]

[ ... ]

PS. For even N, the fastest way to shift by N/2 is almost certainly
just a loop of N/2 swaps in-place as another poster pointed out.

As you'd guess, that's what swap_ranges does (25.2.2/3):

Effects: For each non-negative integer n < (last1 - first1) performs:
swap(*(first1 + n), *(first2 + n))

I see little likelihood that writing the loop yourself will gain
anything.

For
odd N, or for an arbitrary cyclic shift of the array, in the past
we've found that the fastest scheme is to do two in-place passes over
the array: one to reverse the order, and one to un-reverse the two
segments before and after the shift.

Until or unless profiling indicated a necessity to use something else,
I'd use std::rotate. For that matter, I'm not quite sure why your
algorithm would be faster than std::rotate, though I certainly haven't
profiled it to figure out for sure.