Node:Complex One-Dimensional DFTs, Next:Complex Multi-Dimensional DFTs, Previous:Tutorial, Up:Tutorial

### 2.1 Complex One-Dimensional DFTs

> Plan: To bother about the best method of accomplishing an accidental result. [Ambrose Bierce, The Enlarged Devil's Dictionary.]

The basic usage of FFTW to compute a one-dimensional DFT of size `N` is simple, and it typically looks something like this code:

    #include <fftw3.h>
    ...
    {
        fftw_complex *in, *out;
        fftw_plan p;
        ...
        in = fftw_malloc(sizeof(fftw_complex) * N);
        out = fftw_malloc(sizeof(fftw_complex) * N);
        p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE);
        ...
        fftw_execute(p); /* repeat as needed */
        ...
        fftw_destroy_plan(p);
        fftw_free(in); fftw_free(out);
    }

(When you compile, you must also link with the `fftw3` library, e.g. `-lfftw3 -lm` on Unix systems.)

First you allocate the input and output arrays. You can allocate them in any way that you like, but we recommend using `fftw_malloc`, which behaves like `malloc` except that it properly aligns the array when SIMD instructions (such as SSE and Altivec) are available (see SIMD alignment and fftw_malloc).

The data is an array of type `fftw_complex`, which is by default a `double[2]` composed of the real (`in[i][0]`) and imaginary (`in[i][1]`) parts of a complex number.

The next step is to create a plan, which is an object that contains all the data that FFTW needs to compute the FFT. This function creates the plan:

    fftw_plan fftw_plan_dft_1d(int n, fftw_complex *in, fftw_complex *out,
                               int sign, unsigned flags);

The first argument, `n`, is the size of the transform you are trying to compute. The size `n` can be any positive integer, but sizes that are products of small factors are transformed most efficiently (although prime sizes still use an O(n log n) algorithm).

The next two arguments are pointers to the input and output arrays of the transform. These pointers can be equal, indicating an in-place transform.

The fourth argument, `sign`, can be either `FFTW_FORWARD` (`-1`) or `FFTW_BACKWARD` (`+1`), and indicates the direction of the transform you are interested in; technically, it is the sign of the exponent in the transform.

The `flags` argument is usually either `FFTW_MEASURE` or `FFTW_ESTIMATE`. `FFTW_MEASURE` instructs FFTW to run and measure the execution time of several FFTs in order to find the best way to compute the transform of size `n`. This process takes some time (usually a few seconds), depending on your machine and on the size of the transform. `FFTW_ESTIMATE`, on the contrary, does not run any computation and just builds a reasonable plan that is probably sub-optimal. In short, if your program performs many transforms of the same size and initialization time is not important, use `FFTW_MEASURE`; otherwise use the estimate. The data in the `in`/`out` arrays is overwritten during `FFTW_MEASURE` planning, so such planning should be done before the input is initialized by the user.

Once the plan has been created, you can use it as many times as you like for transforms on the specified `in`/`out` arrays, computing the actual transforms via `fftw_execute(plan)`:

    void fftw_execute(const fftw_plan plan);

If you want to transform a different array of the same size, you can create a new plan with `fftw_plan_dft_1d` and FFTW automatically reuses the information from the previous plan, if possible. (Alternatively, with the "guru" interface you can apply a given plan to a different array, if you are careful. See FFTW Reference.)

When you are done with the plan, you deallocate it by calling `fftw_destroy_plan(plan)`:

    void fftw_destroy_plan(fftw_plan plan);

Arrays allocated with `fftw_malloc` should be deallocated by `fftw_free` rather than the ordinary `free` (or, heaven forbid, `delete`).

The DFT results are stored in-order in the array `out`, with the zero-frequency (DC) component in `out[0]`. If `in != out`, the transform is out-of-place and the input array `in` is not modified. Otherwise, the input array is overwritten with the transform.

Users should note that FFTW computes an unnormalized DFT. Thus, computing a forward followed by a backward transform (or vice versa) results in the original array scaled by `n`. For the definition of the DFT, see What FFTW Really Computes.

If you have a C compiler, such as `gcc`, that supports the recent C99 standard, and you `#include <complex.h>` before `<fftw3.h>`, then `fftw_complex` is the native double-precision complex type and you can manipulate it with ordinary arithmetic. Otherwise, FFTW defines its own complex type, which is bit-compatible with the C99 complex type. See Complex numbers. (The C++ `<complex>` template class may also be usable via a typecast.)

Single and long-double precision versions of FFTW may be installed; to use them, replace the `fftw_` prefix by `fftwf_` or `fftwl_` and link with `-lfftw3f` or `-lfftw3l`, but use the same `<fftw3.h>` header file.

Many more flags exist besides `FFTW_MEASURE` and `FFTW_ESTIMATE`. For example, use `FFTW_PATIENT` if you're willing to wait even longer for a possibly even faster plan (see FFTW Reference). You can also save plans for future use, as described by Words of Wisdom-Saving Plans.