C++でコンパイル時合成数和

合成数列の和 Advent Calendarへ参加するにあたって、普段使っている言語は先に取られていることも多かったので、数分間悩んだ結果として「100個しかないなら、C++でコンパイル時に処理してやろう」という結論に達しました。

コンパイル時に処理させるには

C++の特徴として、「コンパイル時に、ソースコードで指示した形の処理を行わせる」ことが可能だという点があります。その方法にもいくつかあります。

プリプロセッサ

#defineや#includeなどのディレクティブを書いて、ソースコードを文字列的に置き換えていく手法です。C言語からの伝統があること、トークンを書き換えるなどC++の文法の枠外のことも可能となるなどのメリットもありますが、あくまで文字列置換なので、数値計算すら面倒です。

テンプレートメタプログラミング

C++で入ったテンプレートを利用して、テンプレートの定義を変数の宣言、分岐は特殊化、のように解釈すれば関数型言語として、チューリング完全なプログラミングが可能となります。ただ、コードは冗長になるし、通常のC++と考え方が大きく違うプログラミングとなります。

constexpr

これはC++11から入った、比較的新しい機能ですが、関数や変数などをconstexprと宣言することでコンパイル時実行が可能となります。少し気をつければ、ふつうのC++で書いたコードをコンパイル時実行できてしまいます。

今回は、constexprで配列を作り出すことで、すべての演算をコンパイル時に解決してしまうことにしました。

constexprなコードを書いていく

素数の判定

C++11のconstexpr関数は「return 式;の一文しか書けない」という制約があったので、「条件分岐は? :で書く」「ループは再帰で表現する」といった特殊な書き方が必要だったのですが、C++14では大幅に制約が緩和され、ローカル変数やループを使うなど、（引数とローカル変数以外ではconstexprなものしか使えない点を除けば）ほとんど普通の関数として書けるようになっています。

constexpr bool isPrime(int num) {
  for(int i = 2; i * i <= num; ++i) {
    if(num % i == 0) return false;
  }
  return true;
}

見てのとおり、constexprを付けていることを除けば、ごく一般的な関数と何ら変わりません。なお、constexpr関数はコンパイル時専用というわけではなく、実行時に使うことも可能です。

配列を作る

配列がファーストクラスでないC++という事情もあって、constexprな配列を直接作ることはできない…のですが、C言語時代に「配列は代入できないけど、配列を含んだ構造体はコピーできた」のと同様、配列を含んだconstexprな構造体やクラスを作ることは可能です。

C++11では、constexprなクラスのコンストラクタには何も書けなかったのですが¹、C++14ではconstexpr関数と同程度のものが書けるようになっています。では、「合成数の和を入れた配列」を含むconstexprな構造体を作ります。配列の要素数はテンプレートにすることで、定数式を供給できる形となります。

template<int N> struct Syntheses {
  int ary[N];
  constexpr Syntheses() : ary() {
    int num = 6, i = 1;
    // 最初1回だけ事前に片付ける
    ary[0] = 4;
    while(i < N) {
      ary[i] = ary[i - 1] + num++;
      i++;
      while(isPrime(num)) num++;      
    }
  }
};

出来上がった定数式を使う

あとは、このSynthesesをconstexprな変数に割り当てれば、コンパイル時に生成するテーブルの一丁上がりです。入出力を付ければ完成です。

int main()
{
    constexpr auto syntheses = Syntheses<100>();
    int i;
    std::cin >> i;
    std::cout << syntheses.ary[i - 1] << std::endl;
}

と、9割ぐらいは普段どおりのC++コードを書いているだけで、計算をコンパイラに任せることができました。

Wandboxでの実装結果

1. メンバの初期化にはメンバイニシャライザを使っていました。 ↩