Can someone write this code with better logic?

Question

I am stuck with this problem for 2 days. Can someone help me with the logic ?

I am working on C++ programs for good algorithms. I am now working on the Danielson-Lanczos Algorithm to compute the FFT of a sequence.

Looking at

mmax=2;
while (n>mmax) {
    istep = mmax<<1;
    theta = -(2*M_PI/mmax);
    wtemp = sin(0.5*theta);
    wpr = -2.0*wtemp*wtemp;
    wpi = sin(theta);
    wr = 1.0;
    wi = 0.0;

    for (m=1; m < mmax; m += 2) {
        for (i=m; i <= n; i += istep) {
            j=i+mmax;
            tempr = wr*data[j-1] - wi*data[j];
            tempi = wr * data[j] + wi*data[j-1];

            data[j-1] = data[i-1] - tempr;
            data[j] = data[i] - tempi;
            data[i-1] += tempr;
            data[i] += tempi;
        }
        wtemp=wr;
        wr += wr*wpr - wi*wpi;
        wi += wi*wpr + wtemp*wpi;
    }
    mmax=istep;
}

Source: http://www.eetimes.com/design/signal-processing-dsp/4017495/A-Simple-and-Efficient-FFT-Implementation-in-C--Part-I

Is there any way to logically write a code such that the whole for-loop portion is reduced to just 4 lines of code (or even better)?

Answer 1

Better indentation would go a long way. I fixed that for you. Also, this seems to beg for better locality of the variables. The variable names are not clear to me, but that might be because I don't know the domain this algorithm belongs to.

Generally, if you want to make complex code easier to understand, identify sub-algorithms and put them into their own (inlined) functions. (Putting a code snippet into a function effectively gives it a name, and makes the passing of variables into and out of the code more obvious. Often, that makes code easier to digest.)
I'm not sure this is necessary for this piece of code, though.

Merely condensing code, however, will not make it more readable. Instead, it will just make it more condensed.

Answer 2

Do not compress your code. Please? Pretty please? With a cherry on top?

Unless you can create a better algorithm, compressing an existing piece of code will only make it look like something straight out of the gates of Hell itself. No one would be able to understand it. You would not be able to understand it, even a few days later.

Even the compiler might get too confused by all the branches to properly optimize it.

If you are trying to improve performance, consider the following:

1. Premature optimization is the source of all evils.

2. Work on your algorithms first, then on your code.

3. The line count may have absolutely no relation to the size of the produced executable code.

4. Compilers do not like entangled code paths and complex expressions. Really...

5. Unless the code is really performance critical, readability trumps everything else.

6. If it is performance critical, profile first, then start optimizing.

Answer 3

You could use a complex number class to reflect the math involved.

A good part of the code is made of two complex multiplications.

You can rewrite your code as :

unsigned long mmax=2;
while (n>mmax)
{
    unsigned long istep = mmax<<1;
    const complex wp = coef( mmax );
    complex w( 1. , 0. );
    for (unsigned long m=1; m < mmax; m += 2)
    {
        for (unsigned long i=m; i <= n; i += istep)
        {
            j=i+mmax;
            complex temp = w * complex( data[j-1] , data[j] );
            complexref( data[j-1] , data[j] ) = complex( data[i-1] , data[i] ) - temp ;
            complexref( data[i-1] , data[i] ) += temp ;
        }
        w += w * wp ;
    }
    mmax=istep;
}

With :

struct complex
{
    double r , i ;
    complex( double r , double i ) : r( r ) , i( i ) {}

    inline complex & operator+=( complex const& ref )
    {
        r += ref.r ;
        i += ref.i ;
        return *this ;
    }
};

struct complexref
{
    double & r , & i ;
    complexref( double & r , double & i ) : r( r ) , i( i ) {}

    inline complexref & operator=( complex const& ref )
    {
        r = ref.r ;
        i = ref.i ;
        return *this ;
    }

    inline complexref & operator+=( complex const& ref )
    {
        r += ref.r ;
        i += ref.i ;
        return *this ;
    }
}    ;

inline complex operator*( complex const& w , complex const& b )
{
    return complex(
        w.r * b.r - w.i * b.i ,
        w.r * b.i + w.i * b.r
    );
}

inline complex operator-( complex const& w , complex const& b )
{
    return complex( w.r - b.r , w.i - b.i );
}
inline complex coef( unsigned long mmax )
{
    double theta = -(2*M_PI/mmax);
    double wtemp = sin(0.5*theta);
    return complex( -2.0*wtemp*wtemp , sin(theta) );
}

Answer 4

1. I don't believe you would be able to make it substantially shorter.
2. If this code were made much shorter, I would guess that it would significantly diminish readability.
3. Since the logic is relatively clear, number of lines does not matter — unless you're planning on using this on codegolf.stackexchange.com, this is a place where you should trust your compiler to help you (because it will)
4. This strikes me as premature optimization.