C++テンプレートで素数計算

re C++のテンプレートで素数計算 - 西尾泰和のはてなダイアリー

西尾さんが書くとか言っていたので自分もやるかと思って書いて、経験の分余裕で先着だろうと思っていたら西尾さんもできていたという。すごいなぁ。

#include <stdio.h>

template<bool Cond, int N> struct CondPrint {
};

template<int N> struct CondPrint<true, N> {
  CondPrint() {
    printf("%d\n", N);
  }
};

template<int N, int D=2, int Mod=N%D> struct IsPrime {
  typedef typename IsPrime<N, D!=2?D+2:3>::Print Print;
};

template<int N, int D> struct IsPrime<N, D, 0> {
  typedef CondPrint<false, N> Print;
};

template<int N> struct IsPrime<N, N, 0> {
  typedef CondPrint<true, N> Print;
};

template<int N> struct PrintPrime {
  PrintPrime() {
    PrintPrime<N-1>();
    typename IsPrime<N>::Print();
  }
};

template<> struct PrintPrime<1> {
};

int main()
{
  PrintPrime<500>();
}

で、西尾さんのコードとコンパイル時間を比べっこしてみると、typedef を使った方が関数呼出を使うより大幅に速いみたい。コード生成まで行うか型の解決だけするか、っていうところの速度差なのかなぁ。逆に、可読性という意味では typedef は劣ると思った。typename とかコンパイラ依存の部分が大きいような気もするし。

ついでに上のコードでは、小さい数から割って行ったり、奇数だけ見たり、といった最適化も入れてみました。

22:43 追記: 上のコード、最適化がバグってる (汗) 修正してついでに数値の生成を単純な再帰から二分割にすることで、実体化のネストの抑制をしてみました。あと typedef 使わなくしたので読みやすくなったかも。

#include <stdio.h>

template<int N, int D=2, int Mod=N<3?-1:N%D> struct IsPrime {
  typedef typename IsPrime<N, D!=2?D+2:3, D*D>=N?-1:N%D>::Print Print;
};

template<int N, int D> struct IsPrime<N, D, 0> {
  struct Print {
  };
};

template<int N, int D> struct IsPrime<N, D, -1> {
  struct Print {
    Print() {
      printf("%d\n", N);
    }
  };
};

template<int D> struct IsPrime<0, D, -1> {
  struct Print {
  };
};

template<int D> struct IsPrime<1, D, -1> {
  struct Print {
  };
};

template<int C, int N=0> struct PrintPrime {
  PrintPrime() {
    PrintPrime<C/2, N>();
    PrintPrime<C-C/2, N+C/2>();
  }
};

template<int N> struct PrintPrime<1, N> {
  PrintPrime() {
    typename IsPrime<N>::Print();
  }
};

int main()
{
  PrintPrime<1000>();
}