Debian Codegraph @

third-party/boost-math/include/boost/math/special_functions/chebyshev_transform.hpp

raw
1 // (C) Copyright Nick Thompson 2017.
2 // Use, modification and distribution are subject to the
3 // Boost Software License, Version 1.0. (See accompanying file
4 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6 #ifndef BOOST_MATH_SPECIAL_CHEBYSHEV_TRANSFORM_HPP
7 #define BOOST_MATH_SPECIAL_CHEBYSHEV_TRANSFORM_HPP
8 #include <cmath>
9 #include <type_traits>
10 #include <boost/math/constants/constants.hpp>
11 #include <boost/math/special_functions/chebyshev.hpp>
12
13 #ifdef BOOST_HAS_FLOAT128
14 #include <quadmath.h>
15 #endif
16
17 #ifdef __has_include
18 # if __has_include(<fftw3.h>)
19 # include <fftw3.h>
20 # else
21 # error "This feature is unavailable without fftw3 installed"
22 #endif
23 #endif
24
25 namespace boost { namespace math {
26
27 namespace detail{
28
29 template <class T>
30 struct fftw_cos_transform;
31
32 template<>
33 struct fftw_cos_transform<double>
34 {
35 fftw_cos_transform(int n, double* data1, double* data2)
36 {
37 plan = fftw_plan_r2r_1d(n, data1, data2, FFTW_REDFT10, FFTW_ESTIMATE);
38 }
39 ~fftw_cos_transform()
40 {
41 fftw_destroy_plan(plan);
42 }
43 void execute(double* data1, double* data2)
44 {
45 fftw_execute_r2r(plan, data1, data2);
46 }
47 static double cos(double x) { return std::cos(x); }
48 static double fabs(double x) { return std::fabs(x); }
49 private:
50 fftw_plan plan;
51 };
52
53 template<>
54 struct fftw_cos_transform<float>
55 {
56 fftw_cos_transform(int n, float* data1, float* data2)
57 {
58 plan = fftwf_plan_r2r_1d(n, data1, data2, FFTW_REDFT10, FFTW_ESTIMATE);
59 }
60 ~fftw_cos_transform()
61 {
62 fftwf_destroy_plan(plan);
63 }
64 void execute(float* data1, float* data2)
65 {
66 fftwf_execute_r2r(plan, data1, data2);
67 }
68 static float cos(float x) { return std::cos(x); }
69 static float fabs(float x) { return std::fabs(x); }
70 private:
71 fftwf_plan plan;
72 };
73
74 template<>
75 struct fftw_cos_transform<long double>
76 {
77 fftw_cos_transform(int n, long double* data1, long double* data2)
78 {
79 plan = fftwl_plan_r2r_1d(n, data1, data2, FFTW_REDFT10, FFTW_ESTIMATE);
80 }
81 ~fftw_cos_transform()
82 {
83 fftwl_destroy_plan(plan);
84 }
85 void execute(long double* data1, long double* data2)
86 {
87 fftwl_execute_r2r(plan, data1, data2);
88 }
89 static long double cos(long double x) { return std::cos(x); }
90 static long double fabs(long double x) { return std::fabs(x); }
91 private:
92 fftwl_plan plan;
93 };
94 #ifdef BOOST_HAS_FLOAT128
95 template<>
96 struct fftw_cos_transform<__float128>
97 {
98 fftw_cos_transform(int n, __float128* data1, __float128* data2)
99 {
100 plan = fftwq_plan_r2r_1d(n, data1, data2, FFTW_REDFT10, FFTW_ESTIMATE);
101 }
102 ~fftw_cos_transform()
103 {
104 fftwq_destroy_plan(plan);
105 }
106 void execute(__float128* data1, __float128* data2)
107 {
108 fftwq_execute_r2r(plan, data1, data2);
109 }
110 static __float128 cos(__float128 x) { return cosq(x); }
111 static __float128 fabs(__float128 x) { return fabsq(x); }
112 private:
113 fftwq_plan plan;
114 };
115
116 #endif
117 }
118
119 template<class Real>
120 class chebyshev_transform
121 {
122 public:
123 template<class F>
124 chebyshev_transform(const F& f, Real a, Real b,
125 Real tol = 500 * std::numeric_limits<Real>::epsilon(),
126 size_t max_refinements = 16) : m_a(a), m_b(b)
127 {
128 if (a >= b)
129 {
130 throw std::domain_error("a < b is required.\n");
131 }
132 using boost::math::constants::half;
133 using boost::math::constants::pi;
134 using std::cos;
135 using std::abs;
136 Real bma = (b-a)*half<Real>();
137 Real bpa = (b+a)*half<Real>();
138 size_t n = 256;
139 std::vector<Real> vf;
140
141 size_t refinements = 0;
142 while(refinements < max_refinements)
143 {
144 vf.resize(n);
145 m_coeffs.resize(n);
146
147 detail::fftw_cos_transform<Real> plan(static_cast<int>(n), vf.data(), m_coeffs.data());
148 Real inv_n = 1/static_cast<Real>(n);
149 for(size_t j = 0; j < n/2; ++j)
150 {
151 // Use symmetry cos((j+1/2)pi/n) = - cos((n-1-j+1/2)pi/n)
152 Real y = detail::fftw_cos_transform<Real>::cos(pi<Real>()*(j+half<Real>())*inv_n);
153 vf[j] = f(y*bma + bpa)*inv_n;
154 vf[n-1-j]= f(bpa-y*bma)*inv_n;
155 }
156
157 plan.execute(vf.data(), m_coeffs.data());
158 Real max_coeff = 0;
159 for (auto const & coeff : m_coeffs)
160 {
161 if (detail::fftw_cos_transform<Real>::fabs(coeff) > max_coeff)
162 {
163 max_coeff = detail::fftw_cos_transform<Real>::fabs(coeff);
164 }
165 }
166 size_t j = m_coeffs.size() - 1;
167 while (abs(m_coeffs[j])/max_coeff < tol)
168 {
169 --j;
170 }
171 // If ten coefficients are eliminated, the we say we've done all
172 // we need to do:
173 if (n - j > 10)
174 {
175 m_coeffs.resize(j+1);
176 return;
177 }
178
179 n *= 2;
180 ++refinements;
181 }
182 }
183
184 inline Real operator()(Real x) const
185 {
186 return chebyshev_clenshaw_recurrence(m_coeffs.data(), m_coeffs.size(), m_a, m_b, x);
187 }
188
189 // Integral over entire domain [a, b]
190 Real integrate() const
191 {
192 Real Q = m_coeffs[0]/2;
193 for(size_t j = 2; j < m_coeffs.size(); j += 2)
194 {
195 Q += -m_coeffs[j]/((j+1)*(j-1));
196 }
197 return (m_b - m_a)*Q;
198 }
199
200 const std::vector<Real>& coefficients() const
201 {
202 return m_coeffs;
203 }
204
205 Real prime(Real x) const
206 {
207 Real z = (2*x - m_a - m_b)/(m_b - m_a);
208 Real dzdx = 2/(m_b - m_a);
209 if (m_coeffs.size() < 2)
210 {
211 return 0;
212 }
213 Real b2 = 0;
214 Real d2 = 0;
215 Real b1 = m_coeffs[m_coeffs.size() -1];
216 Real d1 = 0;
217 for(size_t j = m_coeffs.size() - 2; j >= 1; --j)
218 {
219 Real tmp1 = 2*z*b1 - b2 + m_coeffs[j];
220 Real tmp2 = 2*z*d1 - d2 + 2*b1;
221 b2 = b1;
222 b1 = tmp1;
223
224 d2 = d1;
225 d1 = tmp2;
226 }
227 return dzdx*(z*d1 - d2 + b1);
228 }
229
230 private:
231 std::vector<Real> m_coeffs;
232 Real m_a;
233 Real m_b;
234 };
235
236 }}
237 #endif