P
Ist N bei dir eine Compilezeit-Konstante? Dann kann man den Laufzeit-Aufwand der Rechnungen deutlich reduzieren.
Laut Wikipedia ist eine alternative Darstellung der Polynome
P\_n(x) = \sum\_{k=0}^{k_\mathrm{MAX}} (-1)^k \frac{(2n - 2k)! \ x^{n-2k}}{(n-k)! \ (n-2k)! \ k! \ 2^n}$$, mit $$k_\text{MAX} = \begin{cases} \frac{n}{2} & n \ \text{gerade}\\ \frac{n-1}{2} & n \ \text{ungerade} \end{cases}
Das heißt $$P_n(x) = \sum_{k=0}^{k_\mathrm{MAX}} c(n,k) x^{n-2k}$$ mit $$c(n,k) = (-1)^k \frac{(2n - 2k)! }{(n-k)! \ (n-2k)! \ k! \ 2^n}$$
c rekursiv definiert ergibt $$c(n,k) = c(n,k-1) \cdot -\frac{(n-k+1) \ (n-2k+1)(n-2k+2)}{k(2n-2k+1)(2n-2k+2)}$$ für k>0 und
c(n,0)=(2n)!n! n!2nc(n,0) = \frac{(2n)!}{n! \ n! 2^n}
c(n,0)=n! n!2n(2n)!
Definiert man jetzt $$s(n,i,x) = \sum_{k=0}^{i} c(n,k) x^{n-2k}$$ und $$s(n,0,x) = c(n,0) x^{n}$$
Kann man auch s rekusiv definieren als $$s(n,i,x) = c(n,i) x^{n-2i} + s(n,i-1,x)$$
als einziges "schwierig" zu berechnen (im Sinne von C++-Compilezeit Berechnungen) ist dabei jetzt noch die Potenz von x, die durch eine Hilfsvariable y=x^(n-2i+2) gelöst werden kann:
s(n,i,x,y) = c(n,i) y + s(n,i-1,x, y\*x\*x)
Alles zusammen ergibt sich
P\_n(x) = s(n,k\_\mathrm{MAX},x,y_0)$$ mit $$y_0 = \begin{cases} 1 & n \ \text{gerade}\\ x & n \ \text{ungerade} \end{cases}
Als Template-möglichst-Meta-Programm:
template <int N>
struct fac { enum {value = N*fac<N-1>::value}; };
template <>
struct fac<0> {enum {value = 1};};
template <int N, int I>
struct S
{
const static int c = -( (N-I+1)*(N-2*I+1)*(N-2*I+2) ) / ( I*(2*N-2*I+1)*(2*N-2*I+2) ) * S<N, I-1>::c;
static double eval(double x, double y)
{
return c*y + S<N, I-1>::eval(x, y*x*x);
}
};
template <int N>
struct S<N,0>
{
const static int c = fac<2*N>::value / (fac<N>::value * fac<N>::value * (1<<N));
static double eval(double x, double y)
{
return c*y;
}
};
template <int N>
struct P
{
double operator()(double x)
{
return S<N,N/2>::eval(x, (N%2) ? 1.0 : x);
}
};
Hier werden jetzt bei gegebenem N alle Koeffizienten zur Compilezeit ausgerechnet, zur Laufzeit gibts pro Berechnung N Multiplikationen und N/2 Additionen.
Ungetestet und evtl. noch mit Fehlern...
