Difference between revisions of "CFT"
m (Text replacement - "\$([^\$]+)\$" to "\\(\1\\)") |
|||
| Line 1: | Line 1: | ||
[[CFT]], is the discrete implementation of the [[CosFT]] transform. |
[[CFT]], is the discrete implementation of the [[CosFT]] transform. |
||
| − | At some fixed number |
+ | At some fixed number \(N\!+\!1\) of nodes |
| − | the [[CFT]] of array |
+ | 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 |
+ | 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 |
+ | 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]] <ref>ftp://ftp.cpc.ncep.noaa.gov/wd51we/random_phase/four1.c |
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]] <ref>ftp://ftp.cpc.ncep.noaa.gov/wd51we/random_phase/four1.c |
||
</ref><ref> |
</ref><ref> |
||
| Line 73: | Line 73: | ||
16 8.00010000000000 31.99999999999996 8.00010000000000 |
16 8.00010000000000 31.99999999999996 8.00010000000000 |
||
</nowiki></nomathjax></poem> |
</nowiki></nomathjax></poem> |
||
| − | 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 |
+ | 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 |
+ | 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); |
cosft1(data-1,NP); |
||
| Line 85: | Line 85: | ||
The [[SFT]] algorithm can be used for the numerical approximation of the integral transform, [[CosFT]], in the following way. |
The [[SFT]] algorithm can be used for the numerical approximation of the integral transform, [[CosFT]], in the following way. |
||
| − | Let |
+ | Let \(N\) be large integer, integer power of 2. |
| − | Let |
+ | Let \(d= \pi/N\) be step of integration at the uniform grid, |
| − | let |
+ | let \(x_n=d\,n\) be coordinates of nodes for \(n=0\, .., N\), |
| − | and let |
+ | and let \(f_n=f(x_n)\). |
| − | then, |
+ | 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 |
+ | \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 numerical test of this approximation is suggested in article [[CosFT]], |
||
Latest revision as of 18:44, 30 July 2019
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]
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
Keywords
CFT, CosFT, FFT, Integral transform, Numerical recipes in C, SFT, SinFT