ここで死んだ馬を打ちます。C で整数の累乗を行う典型的な (そして高速な) 方法は、次の古典的な方法です。
int64_t ipow(int64_t base, int exp){
int64_t result = 1;
while(exp){
if(exp & 1)
result *= base;
exp >>= 1;
base *= base;
}
return result;
}
ただし、コンパイル時の整数乗数が必要だったので、先に進み、constexpr を使用して再帰的な実装を作成しました。
constexpr int64_t ipow_(int base, int exp){
return exp > 1 ? ipow_(base, (exp>>1) + (exp&1)) * ipow_(base, exp>>1) : base;
}
constexpr int64_t ipow(int base, int exp){
return exp < 1 ? 1 : ipow_(base, exp);
}
2 番目の関数は、1 未満の指数を予測可能な方法で処理するためだけのものです。この場合、合格exp<0はエラーです。
再帰バージョンは 4 倍遅い
[0,15] の範囲で 10E6 のランダムな値の基数と指数のベクトルを生成し、ベクトルで両方のアルゴリズムの時間を計測します (キャッシュ効果を削除するために時間計測なしの実行を行った後)。最適化を行わない場合、再帰メソッドはループの 2 倍の速度になります。ただし、-O3 (GCC) を使用すると、ループは再帰法よりも 4 倍速くなります。
皆さんへの私の質問は次のとおりです。指数と 0 の基数を処理し、として使用できる、より高速な ipow() 関数を思い付くことができる人はいconstexprますか?
(免責事項: より高速な ipow は必要ありません。ここの賢い人たちが何を思いつくかを知りたいだけです)。