# CFT

**CFT**, is the discrete implementation of the CosFT transform.

At some fixed number $N\!+\!1$ of nodes

the **CFT** of array $f$ of length $N\!+\!1$ appears as $g=\,$**CFT**$(f)$ defined with

$\displaystyle g_m=\frac{f_0+(-1)^mf_N}{2}+\sum_{n=1}^{N-1} \cos\left( \frac{\pi}{N}\, m\, n\right) \, f_n$

If $N\!=\!2^n$ for some integer $n$, then, there exist efficient numerical algorithms for evaluation of this sum.
One of them is called cosft1 and described in the Numerical recipes in C; it is available online, as well as the similar algorithm got SFT ^{[1]}^{[2]}^{[3]}^{[4]}

## Contents |

## Test of **CFT**

#include <stdio.h>

#include <math.h>

#include "scft.cin"

#define NP 16

int main(){ int i;double a[NP+1],b[NP+1],c[NP+1];

for(i=0;i<=NP;i++) {

a[i]=

.0001 // suppress some of these 16 lines and see the result

+1.*cos((M_PI/NP)*i)

+2.*cos(2*(M_PI/NP)*i)

+3.*cos(3*(M_PI/NP)*i)

+4.*cos(4*(M_PI/NP)*i)

+5.*cos(5*(M_PI/NP)*i)

+6.*cos(6*(M_PI/NP)*i)

+7.*cos(7*(M_PI/NP)*i)

+8.*cos(8*(M_PI/NP)*i)

+9.*cos(9*(M_PI/NP)*i)

+10.*cos(10*(M_PI/NP)*i)

+11.*cos(11*(M_PI/NP)*i)

+12.*cos(12*(M_PI/NP)*i)

+13.*cos(13*(M_PI/NP)*i)

+14.*cos(14*(M_PI/NP)*i)

+15.*cos(15*(M_PI/NP)*i)

+16.*cos(16*(M_PI/NP)*i)

;

b[i]=a[i]/8.;

}

cosft1(b-1,NP);

for(i=0;i<=NP;i++) c[i]=b[i];

cosft1(c-1,NP);

for(i=0;i<=NP;i++) printf("%2d %19.14lf %19.14lf %19.14lf\n",i,a[i],b[i],c[i]);

}

Thos code produces the output, that shows, that the **CFT** recovers the amplitude of each mode, encoded with the corresponding cosinusoidal at the input.

0 136.00010000000000 0.00019999999999 136.00010000000000

1 -60.04333445990872 1.00000000000000 -60.04333445990872

2 8.00010000000000 2.00000000000000 8.00010000000000

3 -13.93354801245930 2.99999999999999 -13.93354801245931

4 8.00009999999999 4.00000000000001 8.00009999999999

5 -10.24997430711568 5.00000000000000 -10.24997430711569

6 8.00009999999994 5.99999999999999 8.00009999999994

7 -9.24227542093506 7.00000000000001 -9.24227542093507

8 8.00009999999992 7.99999999999999 8.00009999999992

9 -8.83665683885794 9.00000000000002 -8.83665683885795

10 8.00009999999997 10.00000000000001 8.00009999999997

11 -8.64275107722772 10.99999999999999 -8.64275107722773

12 8.00009999999994 11.99999999999998 8.00009999999994

13 -8.54590960522779 13.00000000000000 -8.54590960522780

14 8.00010000000004 14.00000000000004 8.00010000000004

15 -8.50475027826763 14.99999999999999 -8.50475027826764

16 8.00010000000000 31.99999999999996 8.00010000000000

The 0th column of the output is just number of node; the first column is input with numbers since 2 to 16 encoded with the amplitudes of the cosinusoidals of the corresponding modes. The only 0th amplitude is set to $0.0001$ in order to show, that this corresponds to amplitude $0.00002$, according to the definition. The second column is recovery of these numbers with **CFT** routine. The last, third column represents the second iterate of CFT routine, that reproduces, up to the rounding errors, the identity transform of the array in the First column, $~$CFT(CFT($f$))$\,\approx f~$.

The example shows that the correct call of the routine with array of $N\!+\!1$ numbers denoted with identifier data has the following form:

cosft1(data-1,NP);

There is deep philosophy and, may be, even religion about characters "-1" in the line above; they are discussed in the book Numerical recipes in C and interpreted in terms of storage of arrays in Fortran and C++, and refer to the translation of the code from Fortran to C and/or from C to Fortran. The users who consider this routine as just one of Tools for Outstanding Research and Investigation (TORI) may treat these two characters, "-1", as magic abracadabra that provides the wanted and useful result.

## Application

The SFT algorithm can be used for the numerical approximation of the integral transform, CosFT, in the following way.

Let $N$ be large integer, integer power of 2. Let $d= \pi/N$ be step of integration at the uniform grid, let $x_n=d\,n$ be coordinates of nodes for $n=0\, .., N$, and let $f_n=f(x_n)$.

then, $g=\,$ CosFT$(f)$ can be approximated with

$g(x_m)\approx g_m =\,$**CFT**$(f)_m=\,$ $
\frac{f_0+(-1)^mf_N}{2}+\sum_{n=1}^{N-1} \cos\left( \frac{\pi}{N}\, m\, n\right) \, f_n$

The numerical test of this approximation is suggested in article CosFT, the transformation of self-CFT function, the Gaussian, is described.

## References

- ↑ ftp://ftp.cpc.ncep.noaa.gov/wd51we/random_phase/four1.c
- ↑ ftp://ftp.cpc.ncep.noaa.gov/wd51we/random_phase/realft.c
- ↑ ftp://ftp.cs.stanford.edu/cs/robotics/scohen/nr/sinft.c
- ↑ ftp://ftp.cs.stanford.edu/cs/robotics/scohen/nr/cosft.c

## Keywords

**CFT**,
CosFT,
FFT,
Integral transform,
Numerical recipes in C,
SFT,
SinFT