c - 为什么我的一个功能运行得这么慢？

Question

我正在编写几个方法的实现，以在 C 中使用 GMP 查找数字的自然对数。我有两个函数，都可以工作，但其中一个运行起来比另一个慢很多。问题是我期望更快的那个是最慢的。

下面是两个相关函数，而带有int main 的完整文件可以找到here , 而所需的 ln_2.txt 文件是 here .

void taylor_log(mpf_t R, 
                const mpf_t N, 
                const mpf_t T)
{
    mpf_t x, y, r, pr, tmp, d;
    int n = 1;
    mpf_init(x);
    mpf_init(y);
    mpf_init(tmp);
    mpf_init(d);

    mpf_sub_ui(x, N, 1);
    mpf_init_set(y, x);

    mpf_init_set(r, x);
    mpf_init_set_ui(pr, 0);    

    mpf_sub(d, r, pr);
    mpf_abs(d, d);
    while(mpf_cmp(d, T) > 0)
    {
        mpf_set(pr, r);

        mpf_mul(y, y, x);
        mpf_div_ui(tmp, y, ++n);
        mpf_sub(r, r, tmp);

        mpf_mul(y, y, x);
        mpf_div_ui(tmp, y, ++n);
        mpf_add(r, r, tmp);

        mpf_sub(d, r, pr);
        mpf_abs(d,d);
    }
    printf("%d\n", n);
    mpf_set(R, r);
 }

void hyperbolic_log(mpf_t R,
                    const mpf_t N,
                    const mpf_t T)
{
    mpf_t x, x2, r, pr, tmp, d;
    int n = 1;   
    mpf_init(x);
    mpf_init(x2);
    mpf_init(tmp);
    mpf_init(d);

    mpf_sub_ui(x, N, 1);
    mpf_add_ui(tmp, N, 1);
    mpf_div(x, x, tmp);

    mpf_init_set(r, x);
    mpf_init_set_ui(pr, 0);

    mpf_mul(x2, x, x);

    mpf_sub(d, r, pr);
    mpf_abs(d,d);
    while(mpf_cmp(d, T) > 0)
    {
        mpf_set(pr, r);
        ++n;

        mpf_mul(x, x, x2);
        mpf_div_ui(tmp, x, ++n);
        mpf_add(r, r, tmp);

        mpf_sub(d, r, pr);
        mpf_abs(d,d);
    }
    printf("%d\n", n);
    mpf_mul_ui(R, r, 2);
}

现在，至少在理论上，第二个函数应该运行得更快，因为它每个循环的指令更少，并且由于更快的收敛通常执行更少的循环。这不是我在实践中看到的，因为当我在计算中使用至少 33296 位计算 ln(2) 到 10000 位小数时，两者都给出了正确的结果，但第一种方法在大约 0.150 秒内完成，而第二种方法大约需要1 秒。

我不知道是什么导致一个函数的运行速度比另一个函数慢得多，我们将不胜感激。

编辑:为清楚起见，我忘了提及，在将值传递给函数之前，这些值已标准化为范围 [0.5, 1)。这对于两个函数都是一样的我已经确认这在程序中有效，所以从技术上讲我的问题是当 0.5 被提供给算法时。

Answer 1

运行添加了计时函数的程序，N = 2 的性能下降来自 mpf_mul 操作。

在泰勒的案例中，

mpf_mul(y, y, x);

x 为 -0.5 来自 mpf_get_d_2exp((long *)&e, N)) - 1，在 gmp 结构中有大小为 1，无论要求的精度如何。

在双曲线情况下，

mpf_mul(x, x, x2);

x2 是 0.111... 来自

T  = mpf_get_d_2exp((long *)&e, N))
x  = (T - 1)/(T + 1)
x2 = x * x

在 gmp 结构中具有请求精度的大小。这种情况下的乘法成本要高得多。

编辑

实际上罪魁祸首似乎是 mpf_div(x, x, tmp)，它强制 gmp 使用整个精度。 x2 从 x 计算得到相同的精度，因此 mpf_mul 较慢。