C++TMPを使ってコンパイル時に多倍長フィボナッチ計算。

C++テンプレートメタプログラミング、つまりC++のテンプレート機能を使うと、静的に決定できる計算をコンパイル時にやってのけることができる。

あまりにすごすぎたのでフィボナッチ計算のプログラムを作ったのだが、unsigned long long intではすぐ桁あふれしてしまうので、テンプレート多倍長を組んでフィボナッチ計算。

ただし、FFT多倍長乗算とかまで実装する余裕はないので、行列を使った累乗の方法ではなく、普通の加算による線形時間計算の方法を使った。

今回はfib(700)を求めた。コンパイルには5分ほどかかった。

#include <iostream>

using namespace std;

namespace TMP
{

    template<bool expr, typename IfTrue, typename IfFalse>
    struct select
    {
        typedef int type;
    };

    template<typename IfTrue, typename IfFalse>
    struct select<true, IfTrue, IfFalse>
    {
      typedef IfTrue type;
    };
    template<typename IfTrue, typename IfFalse>
    struct select<false, IfTrue, IfFalse>
    {
      typedef IfFalse type;
    };

    template<typename t, t expr0, t expr1>
    struct lt
    {
        static const bool value = expr0 < expr1;
    };

    template<int rest,unsigned long long int n>
    struct sectionspacer
    {
        static void print(ostream &target) {sectionspacer<rest-1, n/10>::print(target);}
    };
    template<int rest>
    struct sectionspacer<rest,0>
    {
        static void print(ostream &target) {target << "0";sectionspacer<rest-1, 0>::print(target);}
    };
    template<>
    struct sectionspacer<0,0>
    {
        static void print(ostream &target) {}
    };

    //template<>
    struct biguzero
    {
        static const unsigned long long int curr = 0;
        typedef biguzero next;
        static void print(ostream &target) {target<<"0";}
        static bool _print(ostream &target) {return false;}
    };

    template<unsigned long long int acurr, typename anext=biguzero>
    struct biguint
    {
        static const unsigned long long int curr = acurr;
        typedef anext next;
        static void print(ostream &target) {_print(target);}
        static bool _print(ostream &target) {if(anext::_print(target)){sectionspacer<8,acurr>::print(target);}cout<<acurr;return true;}
    };

    //template<typename a, typename b,int cl=0>
    //struct bigplus;

    template<typename a, typename b,unsigned long long int cl=0>
    struct biguplus
    {
        typedef
            typename select<
                lt<unsigned long long int, a::curr+b::curr+cl, 100000000>::value,
                biguint<a::curr+b::curr+cl, typename biguplus<typename a::next, typename b::next, 0>::value>,
                biguint<(a::curr+b::curr+cl)%100000000, typename biguplus<typename a::next, typename b::next, (a::curr+b::curr+cl)/100000000>::value>
            >::type
            value;
    };
    template<>
    struct biguplus<biguzero, biguzero, 0>
    {
        typedef biguzero value;
    };

    template<typename a, unsigned long long int b>
    struct bigudecr
    {
        typedef
            typename select<
                lt<unsigned long long int, a::curr, b>::value,
                biguint<100000000+a::curr-b, typename bigudecr<typename a::next, 1>::value >,
                biguint<a::curr-b, typename a::next>
            >::type
            value;
    };
    template<unsigned long long int b>
    struct bigudecr<biguint<b>, b>
    {
        typedef biguzero value;
    };
    template<unsigned long long int a, unsigned long long int b>
    struct bigudecr<biguint<a>, b>
    {
        typedef biguint<a-b> value;
    };

    template<unsigned long long int n>
    struct bigfib_linear
    {
        typedef typename biguplus<typename bigfib_linear<n-1>::value, typename bigfib_linear<n-2>::value >::value value;
    };
    template<>
    struct bigfib_linear<1>
    {
        typedef biguint<1> value;
    };
    template<>
    struct bigfib_linear<0>
    {
        typedef biguzero value;
    };
};

int main()
{
    cout << "fib(700) = ";
    TMP::bigfib_linear<700>::value::print(cout);
    cout << endl;
    return 0;
}

% time make
g++ -O2 -Wall -ftemplate-depth-2000    fib.cpp   -o fib
make  321.82s user 0.39s system 99% cpu 5:22.42 total
% ./fib;./fib.rb
fib(700) = 87470814955752846203978413017571327342367240967697381074230432592527501911290377655628227150878427331693193369109193672330777527943718169105124275
fib(700) = 87470814955752846203978413017571327342367240967697381074230432592527501911290377655628227150878427331693193369109193672330777527943718169105124275