NAG Library Function Document
nag_fft_real (c06eac) calculates the discrete Fourier transform of a sequence of real data values.
||nag_fft_real (Integer n,
Given a sequence of
real data values
, nag_fft_real (c06eac) calculates their discrete Fourier transform defined by
(Note the scale factor of
in this definition.) The transformed values
are complex, but they form a Hermitian sequence (i.e.,
is the complex conjugate of
), so they are completely determined by
The function nag_multiple_hermitian_to_complex (c06gsc)
may be used to convert a Hermitian sequence to the corresponding complex sequence.
To compute the inverse discrete Fourier transform defined by
this function should be followed by a call of nag_conjugate_hermitian (c06gbc)
to form the complex conjugates of the
nag_fft_real (c06eac) uses the fast Fourier transform (FFT) algorithm (see Brigham (1974)
). There are some restrictions on the value of
(see Section 5
Brigham E O (1974) The Fast Fourier Transform Prentice–Hall
n – IntegerInput
On entry: , the number of data values.
. The largest prime factor of n
must not exceed 19, and the total number of prime factors of n
, counting repetitions, must not exceed 20.
x[n] – doubleInput/Output
On entry: must contain , for .
: the discrete Fourier transform stored in Hermitian form. If the components of the transform
are written as
, then for
is contained in
, and for
is contained in
. Elements of the sequence which are not explicitly stored are given by
. (See also Section 10
fail – NagError *Input/Output
The NAG error argument (see Section 3.6
in the Essential Introduction).
6 Error Indicators and Warnings
At least one of the prime factors of n
is greater than 19.
has more than 20 prime factors.
On entry, .
Some indication of accuracy can be obtained by performing a subsequent inverse transform and comparing the results with the original sequence (in exact arithmetic they would be identical).
8 Parallelism and Performance
The time taken is approximately proportional to , but also depends on the factorization of . nag_fft_real (c06eac) is somewhat faster than average if the only prime factors of are 2, 3 or 5; and fastest of all if is a power of 2.
On the other hand, nag_fft_real (c06eac) is particularly slow if has several unpaired prime factors, i.e., if the ‘square-free’ part of has several factors.
This example reads in a sequence of real data values and prints their discrete Fourier transform (as computed by nag_fft_real (c06eac)), after expanding it from Hermitian form into a full complex sequence. It then performs an inverse transform using nag_fft_hermitian (c06ebc)
and nag_conjugate_hermitian (c06gbc)
, and prints the sequence so obtained alongside the original data values.
10.1 Program Text
Program Text (c06eace.c)
10.2 Program Data
Program Data (c06eace.d)
10.3 Program Results
Program Results (c06eace.r)