メタpowについて補足

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でも一時変数に記録した方が良いのかも知れないですけど.