@subsection Importing and Exporting Wisdom@cindex wisdom, import and export@examplevoid fftw_export_wisdom_to_file(FILE *output_file);fftw_status fftw_import_wisdom_from_file(FILE *input_file);@end example@findex fftw_export_wisdom_to_file@findex fftw_import_wisdom_from_file@code{fftw_export_wisdom_to_file} writes the @code{wisdom} to@code{output_file}, which must be a file open forwriting. @code{fftw_import_wisdom_from_file} reads the @code{wisdom}from @code{input_file}, which must be a file open for reading, andreturns @code{FFTW_SUCCESS} if successful and @code{FFTW_FAILURE}otherwise. In both cases, the file is left open and must be closed bythe caller.  It is perfectly fine if other data lie before or after the@code{wisdom} in the file, as long as the file is positioned at thebeginning of the @code{wisdom} data before import.@examplechar *fftw_export_wisdom_to_string(void);fftw_status fftw_import_wisdom_from_string(const char *input_string)@end example@findex fftw_export_wisdom_to_string@findex fftw_import_wisdom_from_string@code{fftw_export_wisdom_to_string} allocates a string, exports the@code{wisdom} to it in @code{NULL}-terminated format, and returns apointer to the string.  If there is an error in allocating or writingthe data, it returns @code{NULL}.  The caller is responsible fordeallocating the string (with @code{fftw_free}) when she is done withit. @code{fftw_import_wisdom_from_string} imports the @code{wisdom} from@code{input_string}, returning @code{FFTW_SUCCESS} if successful and@code{FFTW_FAILURE} otherwise.Exporting @code{wisdom} does not affect the store of @code{wisdom}. Imported@code{wisdom} supplements the current store rather than replacing it(except when there is conflicting @code{wisdom}, in which case the older@code{wisdom} is discarded). The format of the exported @code{wisdom} is``nerd-readable'' LISP-like ASCII text; we will not document it hereexcept to note that it is insensitive to white space (interested userscan contact us for more details).@cindex LISP@cindex nerd-readable text@xref{FFTW Reference}, for more information, and for a description ofhow you can implement @code{wisdom} import/export for other mediabesides files and strings.The following is a brief example in which the @code{wisdom} is read froma file, a plan is created (possibly generating more @code{wisdom}), andthen the @code{wisdom} is exported to a string and printed to@code{stdout}.@example@{     fftw_plan plan;     char *wisdom_string;     FILE *input_file;     /* open file to read wisdom from */     input_file = fopen("sample.wisdom", "r");     if (FFTW_FAILURE == fftw_import_wisdom_from_file(input_file))          printf("Error reading wisdom!\n");     fclose(input_file); /* be sure to close the file! */     /* create a plan for N=64, possibly creating and/or using wisdom */     plan = fftw_create_plan(64,FFTW_FORWARD,                             FFTW_MEASURE | FFTW_USE_WISDOM);     /* ... do some computations with the plan ... */     /* always destroy plans when you are done */     fftw_destroy_plan(plan);     /* write the wisdom to a string */     wisdom_string = fftw_export_wisdom_to_string();     if (wisdom_string != NULL) @{          printf("Accumulated wisdom: %s\n",wisdom_string);          /* Just for fun, destroy and restore the wisdom */          fftw_forget_wisdom(); /* all gone! */          fftw_import_wisdom_from_string(wisdom_string);          /* wisdom is back! */          fftw_free(wisdom_string); /* deallocate it since we're done */     @}@}@end example@c ************************************************************@node FFTW Reference, Parallel FFTW, Tutorial, Top@chapter FFTW ReferenceThis chapter provides a complete reference for all sequential (i.e.,one-processor) FFTW functions.  We first define the data types uponwhich FFTW operates, that is, real, complex, and ``halfcomplex'' numbers(@pxref{Data Types}).  Then, in four sections, we explain the FFTWprogram interface for complex one-dimensional transforms(@pxref{One-dimensional Transforms Reference}), complexmulti-dimensional transforms (@pxref{Multi-dimensional TransformsReference}), and real one-dimensional transforms (@pxref{RealOne-dimensional Transforms Reference}), real multi-dimensionaltransforms (@pxref{Real Multi-dimensional Transforms Reference}).@ref{Wisdom Reference} describes the @code{wisdom} mechanism forexporting and importing plans.  Finally, @ref{Memory AllocatorReference} describes how to change FFTW's default memory allocator.For parallel transforms, @xref{Parallel FFTW}.@menu* Data Types::                  real, complex, and halfcomplex numbers* One-dimensional Transforms Reference::  * Multi-dimensional Transforms Reference::  * Real One-dimensional Transforms Reference::  * Real Multi-dimensional Transforms Reference::  * Wisdom Reference::            * Memory Allocator Reference::  * Thread safety::               @end menu@c -------------------------------------------------------@node Data Types, One-dimensional Transforms Reference, FFTW Reference, FFTW Reference@section Data Types@cindex real number@cindex complex number@cindex halfcomplex arrayThe routines in the FFTW package use three main kinds of data types.@dfn{Real} and @dfn{complex} numbers should be already known to thereader.  We also use the term @dfn{halfcomplex} to describe complexarrays in a special packed format used by the one-dimensional realtransforms (taking advantage of the @dfn{hermitian} symmetry that arisesin those cases).By including @code{<fftw.h>} or @code{<rfftw.h>}, you will have accessto the following definitions:@exampletypedef double fftw_real;typedef struct @{     fftw_real re, im;@} fftw_complex;#define c_re(c)  ((c).re)#define c_im(c)  ((c).im)@end example@tindex fftw_real@tindex fftw_complexAll FFTW operations are performed on the @code{fftw_real} and@code{fftw_complex} data types.  For @code{fftw_complex} numbers, thetwo macros @code{c_re} and @code{c_im} retrieve, respectively, the realand imaginary parts of the number.A @dfn{real array} is an array of real numbers.  A @dfn{complex array}is an array of complex numbers.  A one-dimensional array @math{X} of@math{n} complex numbers is @dfn{hermitian} if the following propertyholds:@texfor all $0 \leq i < n$, we have $X_i = X^{*}_{n-i}$, where$x^*$ denotes the complex conjugate of $x$.@end tex@ifinfofor all @math{0 <= i < n}, we have @math{X[i] = conj(X[n-i])}.@end ifinfo@ifhtmlfor all 0 &lt;= i &lt; n, we have X<sub>i</sub> = conj(X<sub>n-i</sub>)}.@end ifhtmlHermitian arrays are relevant to FFTW because the Fourier transform of areal array is hermitian.Because of its symmetry, a hermitian array can be stored in half thespace of a complex array of the same size.  FFTW's one-dimensional realtransforms store hermitian arrays as @dfn{halfcomplex} arrays.  Ahalfcomplex array of size @math{n} is@cindex hermitian arraya one-dimensional array of @math{n} @code{fftw_real} numbers.  Ahermitian array @math{X} in stored into a halfcomplex array @math{Y} asfollows.@texFor all integers $i$ such that $0 \leq i \leq n / 2$, we have $Y_i :=\hbox{Re}(X_i)$.  For all integers $i$ such that $0 < i < n / 2$,we have $Y_{n - i} := \hbox{Im}(X_i)$.@end tex@ifinfoFor all integers @math{i} such that @math{0 <= i <= n / 2}, we have@math{Y[i] = Re(X[i])}.  For all integers @math{i} such that @math{0 <i < n / 2}, we have @math{Y[n-i] = Im(X[i])}.@end ifinfo@ifhtmlFor all integers i such that 0 &lt;= i &lt;= n / 2, we haveY<sub>i</sub> = Re(X<sub>i</sub>).  For all integers i such that 0&lt; i &lt; n / 2, we have Y<sub>n-i</sub> = Im(X<sub>i</sub>).@end ifhtmlWe now illustrate halfcomplex storage for @math{n = 4} and @math{n = 5},since the scheme depends on the parity of @math{n}.  Let @math{n = 4}.In this case, we have@tex$Y_0 := \hbox{Re}(X_0)$, $Y_1 := \hbox{Re}(X_1)$,$Y_2 := \hbox{Re}(X_2)$, and $Y_3 := \hbox{Im}(X_1)$.@end tex@ifinfo@math{Y[0] = Re(X[0])}, @math{Y[1] = Re(X[1])},@math{Y[2] = Re(X[2])}, and  @math{Y[3] = Im(X[1])}.@end ifinfo@ifhtmlY<sub>0</sub> = Re(X<sub>0</sub>), Y<sub>1</sub> = Re(X<sub>1</sub>),Y<sub>2</sub> = Re(X<sub>2</sub>), and  Y<sub>3</sub> = Im(X<sub>1</sub>).@end ifhtmlLet now @math{n = 5}.  In this case, we have@tex$Y_0 := \hbox{Re}(X_0)$, $Y_1 := \hbox{Re}(X_1)$,$Y_2 := \hbox{Re}(X_2)$, $Y_3 := \hbox{Im}(X_2)$, and $Y_4 := \hbox{Im}(X_1)$.@end tex@ifinfo@math{Y[0] = Re(X[0])}, @math{Y[1] = Re(X[1])},@math{Y[2] = Re(X[2])}, @math{Y[3] = Im(X[2])}, and@math{Y[4] = Im(X[1])}.@end ifinfo@ifhtmlY<sub>0</sub> = Re(X<sub>0</sub>), Y<sub>1</sub> = Re(X<sub>1</sub>),Y<sub>2</sub> = Re(X<sub>2</sub>), Y<sub>3</sub> = Im(X<sub>2</sub>),and Y<sub>4</sub> = Im(X<sub>1</sub>).@end ifhtml@cindex floating-point precisionBy default, the type @code{fftw_real} equals the C type @code{double}.To work in single precision rather than double precision, @code{#define}the symbol @code{FFTW_ENABLE_FLOAT} in @code{fftw.h} and then recompilethe library.  On Unix systems, you can instead use @code{configure--enable-float} at installation time (@pxref{Installation andCustomization}).@fpindex configure@ctindex FFTW_ENABLE_FLOATIn version 1 of FFTW, the data types were called @code{FFTW_REAL} and@code{FFTW_COMPLEX}.  We changed the capitalization for consistency withthe rest of FFTW's conventions.  The old names are still supported, buttheir use is deprecated.@tindex FFTW_REAL@tindex FFTW_COMPLEX@c -------------------------------------------------------@node One-dimensional Transforms Reference, Multi-dimensional Transforms Reference, Data Types, FFTW Reference@section One-dimensional Transforms ReferenceThe one-dimensional complex routines are generally prefixed with@code{fftw_}.  Programs using FFTW should be linked with @code{-lfftw-lm} on Unix systems, or with the FFTW and standard math libraries ingeneral.@menu* fftw_create_plan::            Plan Creation* Discussion on Specific Plans::  * fftw::                        Plan Execution* fftw_destroy_plan::           Plan Destruction* What FFTW Really Computes::   Definition of the DFT.@end menu@node    fftw_create_plan, Discussion on Specific Plans, One-dimensional Transforms Reference, One-dimensional Transforms Reference@subsection Plan Creation for One-dimensional Transforms@example#include <fftw.h>fftw_plan fftw_create_plan(int n, fftw_direction dir,                           int flags);fftw_plan fftw_create_plan_specific(int n, fftw_direction dir,                                    int flags,                                    fftw_complex *in, int istride,                                    fftw_complex *out, int ostride);@end example@tindex fftw_plan@tindex fftw_direction@findex fftw_create_plan@findex fftw_create_plan_specificThe function @code{fftw_create_plan} creates a plan, which isa data structure containing all the information that @code{fftw}needs in order to compute the 1D Fourier transform. You cancreate as many plans as you need, but only one plan for a givenarray size is required (a plan can be reused many times).@code{fftw_create_plan} returns a valid plan, or @code{NULL}if, for some reason, the plan can't be created.  In thedefault installation, this cannot happen, but it is possibleto configure FFTW in such a way that some input sizes areforbidden, and FFTW cannot create a plan.The @code{fftw_create_plan_specific} variant takes as additionalarguments specific input/output arrays and their strides.  For the lastfour arguments, you should pass the arrays and strides that you willeventually be passing to @code{fftw}.  The resulting plans will beoptimized for those arrays and strides, although they may be used onother arrays as well.  Note: the contents of the in and out arrays are@emph{destroyed} by the specific planner (the initial contents areignored, so the arrays need not have been initialized).@subsubheading Arguments@itemize @bullet@item@code{n} is the size of the transform.  It can be any positive integer. @itemize @minus@itemFFTW is best at handling sizes of the form@ifinfo@math{2^a 3^b 5^c 7^d 11^e 13^f},@end ifinfo@tex$2^a 3^b 5^c 7^d 11^e 13^f$,@end tex@ifhtml2<SUP>a</SUP> 3<SUP>b</SUP> 5<SUP>c</SUP> 7<SUP>d</SUP>        11<SUP>e</SUP> 13<SUP>f</SUP>,@end ifhtmlwhere @math{e+f} is either @math{0} or@math{1}, and the other exponents are arbitrary.  Other sizes arecomputed by means of a slow, general-purpose routine (which neverthelessretains @tex$O(n \lo