CODEWITHSUNDEEP
cfftcode-snippets
Ritchie
Ritchie

Reputation: 15

Can somebody help explain what is happening in this fft code snippet

first post here

I have been looking into the fft and in particular the Rosetta Code C implementation http://rosettacode.org/wiki/Fast_Fourier_transform#C

I have been trying to actually understand the code rather than just copy it however I have a problem with a particular line and more specifically a part of the line.

_fft(out+step, buf+step, n , step*2);

so we have a

typedef double complex cplx;

then an array of type cplx is declared

cplx buf[] = {1, 1, 1, 1, 0, 0, 0, 0};

We have step as an int 1

now the problem I am having understanding is what is happening when the int is added to the cplx

so I wrote a test program

#include <stdio.h>
#include <math.h>
#include <complex.h>

typedef double complex cplx;

void test(cplx buff[]) 
{
    for(int a = 0; a < 8; a++) {
        printf("%g \n", creal(buff[a]));
    }
}

int main(int argc, char **argv)
{
    cplx buff[] = {1,1,1,1,0,0,0,0};

    int step = 1;

    test(buff);

    test(buff + step);

    getchar();

    return 0;
}

what I get is:

1 1 1 1 0 0 0 0
1 1 1 0 0 0 0 2.1231e-314

I cannot make heads or tails of it, I may be missing something pretty fundamental about C99 as I cannot seem to be able to find it on here or by google

Upvotes: 1

Views: 143

Answers (2)

datenwolf
datenwolf

Reputation: 162164

now the problem I am having understanding is what is happening when the int is added to the cplx

Actually the addition is not <int> + <cplx> but <int> + <cplx>* (in words an integer plus a pointer to a complex). So what you're dealing with here is what's called pointer arithmetic. Why a pointer you ask? Because in C array types degrade into a pointer to the array's element type when used in an expression which expects a pointer at its place.

So what is pointer arithmetic?

Well, let' s assume we got an object a which is an array of int (the length doesn't matter, as long as we don't access past its boundaries).

int a[N];

Then pointer arithmetic has been defined that the following three expressions have exactly the same meaning:

*(a + i)
a[i]
i[a]

Yes, the last one is perfectly valid C, go ahead, try it out.

What does it mean for your code snippet. Well for one thing, when you add 1 to the buffer pointer you pass to test, you're adding an offset of one. But since the buffer is only 8 elements long and your test function accesses 8 consecutive elements starting from the pointer given it performs an out-of-bounds access which invokes undefined behavior any in fact anything may legally happen.

Upvotes: 1

Richard Chambers
Richard Chambers

Reputation: 17573

It looks to me like you are calling test twice. The first time with the address of buff[0] and the second time with the address of buff[step] where the variable step is equal to 1 so it is the same as buff[1].

This is why you are seeing the rotated output with 

1 1 1 1 0 0 0
1 1 1 0 0 0 0

I left off the last digit. The last digit in the second line is just garbage after the end of the array or after the last element of the array buff.

buff is an array and if you just specify the name buff then it is treated like a pointer. So in the second call to test you are specifying &buff[step] rather than &buff[0] which is the same as buff.

So buff[step] is the same as *(buff + step) just as buff[0] is the same as *(buff + 0) or just *buff. You can either use the braces to do an index or you can do pointer arithmetic.

Upvotes: 0

Related Questions