fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fst first
  6. #define snd second
  7. #define all(c) ((c).begin()), ((c).end())
  8. #define TEST(s) if (!(s)) { cout << __LINE__ << " " << #s << endl; exit(-1); }
  9.  
  10. using Real = double;
  11. struct Chebyshev {
  12.   static constexpr Real PI = acos(-1.0);
  13.   int n;
  14.   Real a, b;
  15.   vector<Real> c;
  16.   Chebyshev(Real a, Real b, int n) : n(n), a(a), b(b), c(n) { }
  17.  
  18.   template <class F>
  19.   Chebyshev(F f, Real a, Real b, int n = 20) : n(n), a(a), b(b), c(n) {
  20.     vector<Real> h(n);
  21.     for (int k = 0; k < n; ++k) {
  22.       Real y = cos(PI*(k+0.5)/n);
  23.       h[k] = f((b-a)/2*y + (b+a)/2);
  24.     }
  25.     for (int j = 0; j < n; ++j) {
  26.       for (int k = 0; k < n; ++k)
  27.         c[j] += h[k] * cos(PI*j*(k+0.5)/n);
  28.       c[j] *= 2.0/n;
  29.     }
  30.   }
  31.   Real operator()(Real x) const {
  32.     Real y = (2*x - a-b)/(b-a), u = 0, v = 0;
  33.     for (int j = n-1; j >= 1; --j) {
  34.       Real w = 2*y*u - v + c[j];
  35.       v = u; u = w;
  36.     }
  37.     return y*u - v + 0.5*c[0];
  38.   }
  39. };
  40. Chebyshev differentiate(Chebyshev f) {
  41.   Chebyshev g = f;
  42.   g.c[f.n-2] = 2 * (f.n-1) * f.c[f.n-1];
  43.   for (int j = f.n-3; j >= 0; --j) 
  44.     g.c[j] = g.c[j+2] + 2 * (j+1) * f.c[j+1];
  45.   for (int j = 0; j < g.n; ++j)
  46.     g.c[j] *= 2.0/(g.b - g.a);
  47.   return g;
  48. }
  49. Chebyshev integrate(Chebyshev f) {
  50.   Chebyshev g = f;
  51.   Real sum = 0, coef = (f.b-f.a)/4, sign = 1.0;
  52.   for (int j = 1; j <= g.n-2; ++j) {
  53.     g.c[j] = coef * (f.c[j-1] - f.c[j+1]) / j;
  54.     sum += sign * g.c[j];
  55.     sign = -sign;
  56.   }
  57.   g.c[f.n-1] = coef * f.c[f.n-2] / (f.n-1);
  58.   sum += sign * g.c[f.n-1];
  59.   g.c[0] = 2 * sum;
  60.   return g;
  61. }
  62. int main() {
  63.   Chebyshev f([](double x) { return sin(x); }, 0, 2*M_PI);
  64.   Chebyshev df = differentiate(f);
  65.  
  66.   cout << fixed << setprecision(15);
  67.   cout << 2 * df(M_PI/4) << endl;
  68. }
  69.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1.414213562373070
https://ideone.com/PtJBnD
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!