2012-07-31 19 views
6

コンパイル時に整数の階乗を計算するための再帰的なテンプレートを実装しました(私は実際にそれが必要になると思っていました)。それでも、自分自身を転がす代わりに、私は答えを探してBoostに行きました。しかし、特別な数学の階乗関数は、整数型の使用を特に禁じているので、私は自分自身で書きました。コンパイル時に小さな整数の階乗を計算する

まだ、Boostには別の機能を使用する必要がありますか?整数をdoubleにキャストし、boost::factorial関数を使用する必要がありますか?コンパイル時に計算が実行されていますか?

+0

テンプレートが反復できる深さが限られているので、コンパイル時の階乗計算からのスピードアップはそれほど大きくはありません(動的プログラミングを使用する場合は特にそうです)。 –

+0

この質問の "R .."の回答を参照してください:http://stackoverflow.com/questions/3786207/howto-compute-the-factorial-of-x。オーバーフローは非常に可能性が高いですなぜBoostはあなたがこれのためにintを使用することを望んでいません。 – mwigdahl

+0

@mwigdahl私は20までフィットすることができます! (しかし、オーバーフローをチェックすることは、私がライブラリ関数を使うことを好む理由の1つになるでしょう、私の実装はそれをチェックしません)。 – gnzlbg

答えて

9

あなたがC++ 11を持っている場合、これはわずか1ライナーで、ブーストを必要としません:

constexpr uint64_t factorial(uint64_t n) { 
    return n == 0 ? 1 : n * factorial(n-1); 
} 

そして、それはあなたのargはあまりにも一定の時間をコンパイルされていない場合でも動作します。 uint64_tはnと一緒に動作します< 21.

コンパイル時に浮動小数点値を掛けている場合、変換のオーバーヘッドはありません(変換時もコンパイル時になります)。

3

整数の中に入ることができる階乗が限られているため、最初の20個の値を手作業で事前計算して、グローバルまたは静的配列に格納するだけで済みます。次に、配列内の階乗をルックアップするために、グローバルまたは静的関数を使用する:あなたはfactorialの引数としてリテラルを使用

#include <iostream> 

const int factorials[] = 
{ 
    1, 
    1, 
    2, 
    6, 
    24, 
    // etc... 
}; 

inline const int factorial(int n) {return factorials[n];} 

int main() 
{ 
    static const int fourFactorial = factorial(4); 
    std::cout << "4! = " << fourFactorial << "\n"; 
} 

場合は、最適化が有効になっている場合、コンパイラは、単純に(結果と関数呼び出しを置き換える必要があります)。私は(Macの)XCodeの4.4で上記の例を試みたと私はそれが定数24とfourFactorialを初期化アセンブリに参照:

.loc 1 20 38 ## /Users/emile/Dev/sandbox/sandbox/main.cpp:20:38 
movl $24, __ZZ4mainE13fourFactorial(%rip) 

この方法は、高速コンパイルをもたらすことができるよりも再帰コンパイル時間を用いてトリック。

関連する問題