メタプログラミングによるべき和計算（3）

昨日たまたま寄った書店でこの本を買った。

C++テンプレートテクニック

テンプレートを使ってはいるが、よく基礎がわかっていないという危ない状態なので、この本を読んでちとなんとかしたい。

さて、以前テンプレートでべき和を関数を求めたが、Pythonで公式を求めてそれをべた書きするより3倍時間がかかってしまっていた。よく考えたら、こういう風にすればべた書きするのと同じになるのではないだろうか。

例えば、

f_n(x) = x + ... + nxⁿ

ときに、

g_n,0(x) = n
g_n,m(x) = g_n,m-1(x) * x + (n - m)
f_n(x) = g_n,n(x)

とする。コードはこう。

#include 
template

int f(int x) {

    return g()(x);

}
template

struct g {

    int operator()(int x) {

        return g()(x) * x + N - M;

    }

};
template

struct g {

    int operator()(int x) {

        return N;

    }

};
int main() {

    for(int i = 0; i <= 10; i++)

        std::cout << f<8>(i) << std::endl;

}

べき和の場合は、あと係数をがんばって求めればよいだけ。かなり地道にがんばってコードを書いたら、公式を埋め込むのと同じスピードが出た（VC2008、オプション /EHsc /O2）。

#include 

#include 
#pragma comment( lib, "winmm.lib" )
// 分母を正にするための処理

template

struct SIGN {

    enum { Val = SIGN<-N,M,(M*N<=0)>::Val };

};
template

struct SIGN {

    enum { Val = N };

};
template

struct GCD {

    enum { Val = GCD::Val>::Val };

};
template

struct GCD {

    enum { Val = N };

};
template

struct LCM {

    enum { Val = N * M / GCD::Val };

};
template

struct C {

    enum { Val = C::Val * (N - M + 1) / M };

};
template

struct C {

    enum { Val = 1 };

};
template

struct FRACTION {

    enum { Num = N / GCD::Val, Den = M / GCD::Val };

};
template

struct TC {

    enum { Num = FRACTION::Num*TC::Den*L

                - C::Val*TC::Den*TC::Num,

                TC::Den*TC::Den*L>::Num,

           Den = FRACTION::Num*TC::Den*L

                - C::Val*TC::Den*TC::Num,

                TC::Den*TC::Den*L>::Den

    };

};
template

struct TC {

    enum { Num = C::Val, Den = 1 };

};
template

struct TC {

    enum { Num = 0, Den = 1 };

};
template

struct SC {

    enum { Num = FRACTION::Num,TC::Den*(N+1)>::Num,

           Den = FRACTION::Num,TC::Den*(N+1)>::Den };

};
// べき和式の分母

template

struct CD {

    enum { Val = LCM::Den,CD::Val>::Val };

};
template

struct CD {

    enum { Val = SC::Den };

};
// 求める式

template

int S(int x) {

    return SF()(x) / CD::Val;

}
template

struct SF {

    int operator()(int x) {

        return SF()(x) * x

            + SC::Num * CD::Val / SC::Den;

    }

};
template

struct SF {

    int operator()(int x) {

        return SC::Num * CD::Val / SC::Den;

    }

};
int main() {

    const int   N = 10000000;

    int sum = 0;

    int t = timeGetTime();

    for(int i = 0; i < N; i++) {

        int n = (rand() % 8 - 4);

        sum += S<5>(n);

    }

    std::cout << sum << std::endl;

    std::cout << (timeGetTime() - t) * 1e-3 << "s" << std::endl;

}