アッカーマン関数
C++をいじる機会があって，前々から気になっていた定数式(constexpr)にもちょっと触れてみた．
なにやら，コンパイル時に値が決定できる値をコンパイル時に計算することで，実行時の速度が早くなるとかなんとか．
アッカーマン関数を実装した．
//ack.cpp #include <iostream> constexpr int ack(int m, int n) { return m == 0 ? n+1 : n == 0 ? ack(m-1, 1) : ack(m-1, ack(m, n-1)); } int main(void) { constexpr int res = ack(3, 7); std::cout << res << std::endl; return 0; }
Ack(3,6)を求めるプログラム．
C++11では定数式に書けるものは実質return文ひとつのみらしい*1ので，条件演算子を数億年ぶりに使った．
こちらは定数式を使わないバージョン．
//ack-o.cpp #include <iostream> int ack(int m, int n) { return m == 0 ? n+1 : n == 0 ? ack(m-1, 1) : ack(m-1, ack(m, n-1)); } int main(void) { std::cout << ack(3, 7) << std::endl; return 0; }
さて，肝心の実行速度だが，
$ time ./ack 1021 real 0m0.002s user 0m0.000s sys 0m0.000s $ time ./ack-o 1021 real 0m0.011s user 0m0.010s sys 0m0.000s
constexprを使ったほうが実行時間は速い．ただし，ack(4,1)のように再帰深度を深くすると，コンパイル時に
ack.cpp:10:33: エラー: constexpr evaluation depth exceeds maximum of 512 (use -fconstexpr-depth= to increase the maximum)
というエラーが出る．constexpr修飾された関数は再帰深度の上限がデフォルトでは512までらしい*2．試しにめちゃめちゃ大きくしてみると通った．
$time g++ -o ack ack.cpp -fconstexpr-depth=100000000 real 0m0.777s user 0m0.703s sys 0m0.067s
実行時計算と比べてみると
$ time ./ack-o 65533 real 0m18.664s user 0m18.657s sys 0m0.003s
実行時計算と同じことをさせているのに，コンパイル時計算の方が圧倒的に速い．
何がキモなんだろう．
