c06 Chapter Contents
c06 Chapter Introduction
NAG C Library Manual

# NAG Library Function Documentnag_fft_real (c06eac)

## 1  Purpose

nag_fft_real (c06eac) calculates the discrete Fourier transform of a sequence of $n$ real data values.

## 2  Specification

 #include #include
 void nag_fft_real (Integer n, double x[], NagError *fail)

## 3  Description

Given a sequence of $n$ real data values ${x}_{\mathit{j}}$, for $\mathit{j}=0,1,\dots ,n-1$, nag_fft_real (c06eac) calculates their discrete Fourier transform defined by
 $z^k = 1n ∑ j=0 n-1 xj exp -i 2πjk n , k= 0, 1, …, n-1 .$
(Note the scale factor of $\frac{1}{\sqrt{n}}$ in this definition.) The transformed values ${\stackrel{^}{z}}_{k}$ are complex, but they form a Hermitian sequence (i.e., ${\stackrel{^}{z}}_{n-k}$ is the complex conjugate of ${\stackrel{^}{z}}_{k}$), so they are completely determined by $n$ real numbers.
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
 $w^k = 1n ∑ j=0 n-1 xj exp +i 2πjk n , for ​ k= 0, 1, …, n-1 ,$
this function should be followed by a call of nag_conjugate_hermitian (c06gbc) to form the complex conjugates of the ${\stackrel{^}{z}}_{k}$.
nag_fft_real (c06eac) uses the fast Fourier transform (FFT) algorithm (see Brigham (1974)). There are some restrictions on the value of $n$ (see Section 5).

## 4  References

Brigham E O (1974) The Fast Fourier Transform Prentice–Hall

## 5  Arguments

1:     nIntegerInput
On entry: $n$, the number of data values.
Constraint: ${\mathbf{n}}>1$. 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.
2:     x[n]doubleInput/Output
On entry: ${\mathbf{x}}\left[\mathit{j}\right]$ must contain ${x}_{\mathit{j}}$, for $\mathit{j}=0,1,\dots ,n-1$.
On exit: the discrete Fourier transform stored in Hermitian form. If the components of the transform ${\stackrel{^}{z}}_{k}$ are written as ${a}_{k}+{ib}_{k}$, then for $0\le k\le n/2$, ${a}_{k}$ is contained in ${\mathbf{x}}\left[k\right]$, and for $1\le k\le \left(n-1\right)/2$, ${b}_{k}$ is contained in ${\mathbf{x}}\left[n-k\right]$. Elements of the sequence which are not explicitly stored are given by ${a}_{n-k}={a}_{k}$, ${b}_{n-k}=-{b}_{k}$, ${b}_{o}=0$ and, if $n$ is even, ${b}_{n/2}=0$. (See also Section 9.)
3:     failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

## 6  Error Indicators and Warnings

NE_C06_FACTOR_GT
At least one of the prime factors of n is greater than 19.
NE_C06_TOO_MANY_FACTORS
n has more than 20 prime factors.
NE_INT_ARG_LE
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}>1$.

## 7  Accuracy

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).

The time taken is approximately proportional to $n\mathrm{log}n$, but also depends on the factorization of $n$. nag_fft_real (c06eac) is somewhat faster than average if the only prime factors of $n$ are 2, 3 or 5; and fastest of all if $n$ is a power of 2.
On the other hand, nag_fft_real (c06eac) is particularly slow if $n$ has several unpaired prime factors, i.e., if the ‘square-free’ part of $n$ has several factors.

## 9  Example

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.

### 9.1  Program Text

Program Text (c06eace.c)

### 9.2  Program Data

Program Data (c06eace.d)

### 9.3  Program Results

Program Results (c06eace.r)