再帰算術メタ関数の再帰停止条件

C++ Boost TMP

a(n) = a(n-1), a(0) = 1で定義される簡単な数列を模した算術メタ関数を作ろうとした．今回，static constな定数（value）を内部に持たずに，あくまでメタ関数としてのみの機能（type）を提供するメタ関数を作ることにこだわってみた．なので，入力・出力はboost::mpl::int_を想定．要するに「型->型」のみにこだわっている．

// 漸化式a(n) = a(n-1)を表現するメタ関数
template<class T>
struct a
{
  typedef
    typename a<
      typename boost::mpl::minus<
        T,
        boost::mpl::int_<1>
      >::type
    >::type
    type
    ;
};

// 再帰停止条件a(0) = 1
template<>
struct a<boost::mpl::int_<0> >
{
  typedef boost::mpl::int_<1> type;
};

ところがこれがうまく動かない．（少なくともVC++7.1では）
色々試行錯誤した結果，再帰停止条件が厳しすぎる（boost::mpl::int_<0>の特殊化にドンピシャで一致しないといけない）のかと思って，SFINAEで若干緩い停止条件を書いてみた．そしたらうまく動いた．

// a(n) = a(n-1)
template<class T, class = void>
struct a
{
  typedef
    typename a<
      typename boost::mpl::minus<
        T,
        boost::mpl::int_<1>
      >::type
    >::type
    type
    ;
};

// a(0) = 1
template<class T>
struct a<
  T,
  typename boost::enable_if<typename boost::mpl::equal_to<T, boost::mpl::int_<0> >::type>::type
>
{
  typedef boost::mpl::int_<1> type;
};

int main()
{
  std::cout << a<boost::mpl::int_<10> >::type::value << std::endl; // a(10)，つまり1
}

（゜д゜）ウマー．

で

C++ Boost TMP

上を踏まえて実際にやりかったのが以下．

#include <boost/utility/enable_if.hpp>
#include <boost/mpl/arithmetic.hpp>
#include <boost/mpl/bitwise.hpp>
#include <boost/mpl/comparison.hpp>
#include <boost/mpl/int.hpp>
#include <iostream>

typedef boost::mpl::int_<0> zero;
typedef boost::mpl::int_<1> one;

// pow(m, n) = pow(m, n & 1) * pow(m, n >> 1) * pow(m, n >> 1)
template<class T1, class T2, class = void>
struct pow
  : public
  boost::mpl::multiplies<
    typename pow<
      T1,
      typename boost::mpl::bitand_<T2, one>::type
    >::type,
    typename pow<
      T1,
      typename boost::mpl::shift_right<T2, one>::type
    >::type,
    typename pow<
      T1,
      typename boost::mpl::shift_right<T2, one>::type
    >::type
  >
{ };

// pow(m, 0) = 1
template<class T1, class T2>
struct pow<
  T1,
  T2,
  typename boost::enable_if<typename boost::mpl::equal_to<T2, zero>::type>::type
>
{
  typedef one type;
};

// pow(m, 1) = n
template<class T1, class T2>
struct pow<
  T1,
  T2,
  typename boost::enable_if<typename boost::mpl::equal_to<T2, one>::type>::type
>
{
  typedef T1 type;
};

int main()
{
  std::cout
    << pow<boost::mpl::int_<2>, boost::mpl::int_<10> >::type::value
    << std::endl; // pow(2, 10) = 1024
  std::cout
    << pow<boost::mpl::int_<3>, boost::mpl::int_<6> >::type::value
    << std::endl; // pow(3, 6) = 729
}

（゜д゜）ウマー．

  • pow(m, n) = pow(m, n & 1) * pow(m, n >> 1) * pow(m, n >> 1)
  • pow(m, 0) = 1
  • pow(m, 1) = m

で定義される数列をメタ関数で表現したもの．要するにpow(m, n) = m^n．もちろん完全にコンパイル時計算．

メタpowについて補足

C++ TMP NC

id:Cryolite:20040923#p1のメタpowについて若干補足．整数べきの高速な算法として例えば2^10を

  1. 2^10 = 2^(2+8) = 2^2 * 2^8に分解
  2. 2*2を計算
  3. 2^4を2.で計算した2^2を使って（平方して）計算
  4. 2^8を3.で計算した2^4を使って計算
  5. 2^2と2^8を乗じて2^10を計算

というのがありますが，上のpowの再帰的な定義はこれに基づいています．この算法は乗算の回数が少ない利点がありますが，メタ関数の文脈だとさらにテンプレートのインスタンス化とインスタンスの数を少なくするという利点もあります．
で，上のpowを普通の関数の形で書くと

int pow(int m, int n)
{
  if(n == 0) return 1;
  if(n == 1) return m;
  int tmp = pow(m, n >> 1);
  return pow(m, n & 1) * tmp * tmp;
}

って感じになるかと思います．普通の関数の場合，pow(m, n >> 1)の評価を一時変数に取っておいてそれを自乗することで関数の評価を1回で済ませます．
ですがメタ関数の場合だと若干事情が違うと考えます．

  • クラステンプレート <-> 関数
  • テンプレートの引数 <-> 関数の引数
  • テンプレートのインスタンス化 <-> 関数の評価
  • ネストtypedefの"type" <-> 関数の戻り値

の対応を踏まえた上で，「一度インスタンス化したクラスを次にlookupするときはもはやインスタンス化する必要がない」という事実を考えると，クラステンプレートによるメタ関数というのは「あらゆる引数に対する結果を記録していて，同じ引数に対する2度目以降の評価はなされず記録している結果を返す」ものとみなせると思います．
となるとメタpowの方はpow(m, n >> 1)の結果をテンポラリに記録する必要が無く，pow(m, n >> 1)を単純に2回呼び出す形でも普通の関数の形と同じ程度に効率的だと思うんですがどうなんでしょうか？
ま，コンパイラ内部でのテンプレートのインスタンスの持ち方やインスタンスのlookupの方法によるので，確実にやろうとするとメタpowでも一時変数に記録した方が良いのかも知れないですけど．

量子テレポーテーション

その他 Physics QC

http://headlines.yahoo.co.jp/hl?a=20040923-00000301-yom-soci
というかid:quantumよ．量子テレポーテーションのキーワードの説明の後半はどう見ても「少々」専門的どころじゃあないだろうｗ．
「古典情報の送信によって量子情報を移動できる」って捉え方でえぇの？それなら光速度超えられないのは当たり前だし．
で，これが完全暗号通信に使えるのは分かるのだが通信の高速化にはどうつながるのかぇ？