优化sqrt(n) - sqrt(n-1)

Question

下面是每秒多次调用的函数：

static inline double calculate_scale(double n) { //n may be int or double
    return sqrt(n) - sqrt(n-1);
}

循环调用，类似：

for(double i = 0; i < x; i++) {
    double scale = calculate_scale(i);
    ...
}

而且太慢了。优化这个函数以获得尽可能精确的输出的最佳方法是什么？

参数n：从1开始，几乎不受限制，但主要用于1-10范围内的小数字。它是整数(整数)，但可能是int或double，这取决于性能更好的是什么。

Answer 1

您可以尝试用下面的近似替换它

sqrt(n) - sqrt(n-1) == 
(sqrt(n) - sqrt(n-1)) * (sqrt(n) + sqrt(n-1)) / (sqrt(n) + sqrt(n-1)) ==
(n - (n + 1)) / (sqrt(n) + sqrt(n-1)) ==
1 / (sqrt(n) + sqrt(n-1))

对于足够大的n，最后一个方程非常接近1 / (2 * sqrt(n))。所以你只需要打一次电话给sqrt。同样值得注意的是，即使没有近似，对于较大的n，最后一个表达式在相对误差方面也更为稳定。

Answer 2

首先，谢谢大家的建议。我做了一些研究，发现了一些有趣的实现和事实。

1.循环或使用预先计算的表

(谢谢@Ulysse )您可以通过简单地保存以前的sqrt(n)值来优化循环。下面的示例演示用于设置预计算表的优化。

    /**
     * Init variables
     *      i       counter
     *      x       number of cycles (size of table)
     *      sqrtI1  previous square root = sqrt(i-1)
     *      ptr     Pointer for next value
     */
    double i, x = sizeof(precomputed_table) / sizeof(double);
    double sqrtI1 = 0;

    double* ptr = (double*) precomputed_table;

    /**
     * Optimized calculation
     * In short:
     *      scale = sqrt(i) - sqrt(i-1)
     */
    for(i = 1; i <= x; i++) {
        double sqrtI = sqrt(i);
        double scale = sqrtI - sqrtI1; 
        *ptr++ = scale;
        sqrtI1 = sqrtI;
    }

使用预先计算的表可能是最快的方法，但它的缺点可能是它的大小是有限的。

static inline double calculate_scale(int n) {
    return precomputed_table[n-1];
}

2.用逆平方根逼近大数

所需逆(倒数)平方根函数rsqrt

该方法具有数值大、精度高的特点。如果数字不多，就会出现错误：

1    2     3      10       100     1000
0.29 0.006 0.0016 0.000056 1.58e-7 4.95e-10

下面是我用来计算上面结果的JS代码：

function sqrt(x) { return Math.sqrt(x); } function d(x) { return (sqrt(x)-sqrt(x-1))-(0.5/sqrt(x-0.5));} console.log(d(1), d(2), d(3), d(10), d(100), d(1000));

您还可以在单个图中看到与两个sqrt版本相比的准确性：https://www.google.com/search?q=(sqrt(x)-sqrt(x-1))-(0.5%2Fsqrt(x-0.5))。

用法：

static inline double calculate_scale(double n) {
    //Same as: 0.5 / sqrt(n-0.5)
    //but lot faster
    return 0.5 * rsqrt(n-0.5);
}

在一些较旧的cpus上(使用缓慢的或没有硬件平方根的cpus)，使用floats和来自Quake的快速逆平方根，您可能会走得更快：

static inline float calculate_scale(float n) {
    return 0.5 * Q_rsqrt(n-0.5);
}

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

有关实现的更多信息，请参见https://en.wikipedia.org/wiki/Fast_inverse_square_root和http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf。不建议在https://stackoverflow.com/a/6666843/7485966上使用。

不总是解: 0.5 / sqrt(n-0.5)

请注意，在一些处理器(例如。( ARM皮质A9，英特尔Core2)除法与硬件平方根几乎相同，所以最好使用2平方根sqrt(n) - sqrt(n-1)的原始函数，如果存在0.5 * rsqrt(n-0.5)，则使用带有乘法的倒数平方根。

3.使用带后备的预算法表

这种方法在前两个解之间是很好的折衷。具有良好的精度和性能。

static inline double calculate_scale(double n) {
    if(n <= sizeof_precomputed_table) {
        int nIndex = (int) n;
        return precomputed_table[nIndex-1];
    }
    //Multiply + Inverse Square root
    return 0.5 * rsqrt(n-0.5);
    //OR
    return sqrt(n) - sqrt(n-1);
}

在我的例子中，我需要非常准确的数字，所以我的预先计算的表大小是2048。

欢迎任何反馈意见。

Answer 3

您曾经说过，n主要是小于10的一个数字。您可能会对小于10的数字使用一个预先计算的表，甚至更多，因为它很便宜，并且在较大的数字情况下可以使用实际的计算。

代码看起来类似于：

static inline double calculate_scale(double n) { //n may be int or double
    if (n <= 10.0 && n == floor(n)) {
        return precomputed[(int) n]
    }
    return sqrt(n) - sqrt(n-1);
}