c++ - 我需要非常快地计算斯特林的近似值

Question

我正在编写一个用于统计抽样的小型库，它需要尽可能快地运行。在分析中，我发现该函数大约 40% 的时间花在了计算 Stirling's approximation 上。对于阶乘的对数。我将我的优化工作集中在这一部分上。这是我的代码(使用 MPFR ):

const double AL[8] =
{ 0.0, 0.0, 0.6931471806, 1.791759469, 3.178053830, 4.787491743,
    6.579251212, 8.525161361 };
void HGD::mpfr_afc(mpfr_t &ret, const mpfr_t &val){

    if(mpfr_cmp_ui(val, 7) <= 0){
        mpfr_set_d(ret, AL[mpfr_get_ui(val, MPFR_RNDN)], MPFR_RNDN);
    }else{
        mpfr_set(ret, val, MPFR_RNDN);
        mpfr_add_d(ret, ret, 0.5, MPFR_RNDN);
        mpfr_log(LV, val, MPFR_RNDN);
        mpfr_mul(ret, LV, ret, MPFR_RNDN);
        mpfr_sub(ret, ret, val, MPFR_RNDN);
        mpfr_add_d(ret, ret, 0.399089934, MPFR_RNDN);
    }
}

我有几个不同的想法:

• 预先计算函数的前 8 个以上的输入。
• 优化数学(使用更粗略的近似值以获得更小的精度)
• 使用多个线程并行计算不同的输入
• 当数字适合机器数据类型时，切换到原生算术

我可以采取其他方法吗？

Answer 1

Switch to native arithmetic when numbers can fit in machine data types

那将是我的第一次尝试。 MPFR 可能会成为性能 killer 。

在我看来，您想计算 n 的对数!您已经使用斯特林公式对其进行了近似。

请注意 n!=Gamma(n+1)。有(看似)高度优化的函数来计算 Gamma 函数及其对数。例如:

• Standard C++11 lgamma
• Boost lgamma
• GNU GSL lngamma
• TOMS 291
• http://www.johndcook.com/cpp_gamma.html

只有当上述所有方法在性能方面都失败时，我才会推出我自己的粗略近似值。