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[i];
for (i=N-1;i>=del;i--) A1[i]=A1[i-del];
for (i=0;i<del;i++) A1[i]=D[i];
}
else if(del<0 && del -N)
{
del=-del;
for (i=0;i<del;i++) D[i]=A1[i];
for (i=0;i<N-del;i++) A1[i]=A1[i+del];
for (i=N-del;i<N;i++) A1[i]=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

[Victor Bazarov]

Matthias Pospiech wrote:

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.

You might consider using swap N/2 times, in place, instead of
allocating another array and doing so many loops:

for (int i = 0, half = N/2; i < half; ++i)
swap(A[i], A[i + half]);

Now, you didn't say what should happen if the array has an odd
number of elements, so please adjust the loop accordingly.

[..]

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Jerry Coffin]

In article <fv**********@newsserver.rrzn.uni-hannover.de>, matthias79
@gmx.de says...

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.

--
Later,
Jerry.

The universe is a figment of its own imagination.