固定点的逆平方根 [英] Inverse sqrt for fixed point

问题描述

我正在寻找固定点16.16数的最佳逆平方根算法.到目前为止，下面的代码是我所拥有的(但是基本上，它取平方根并除以原始数，我想得到不除数的平方根倒数).如果更改了任何内容，则将为armv5te编译代码.

I am looking for the best inverse square root algorithm for fixed point 16.16 numbers. The code below is what I have so far(but basically it takes the square root and divides by the original number, and I would like to get the inverse square root without a division). If it changes anything, the code will be compiled for armv5te.

uint32_t INVSQRT(uint32_t n)
{
    uint64_t op, res, one;
    op = ((uint64_t)n<<16);
    res = 0;
    one = (uint64_t)1 << 46;
    while (one > op) one >>= 2;
    while (one != 0)
    {
        if (op >= res + one)
        {
            op -= (res + one);
            res +=  (one<<1);
        }
        res >>= 1;
        one >>= 2;
    }
    res<<=16;
    res /= n;
    return(res);
}

推荐答案

技巧是将牛顿方法应用于问题x-1/y ^ 2 =0.因此，给定x，使用迭代方案求解y.

The trick is to apply Newton's method to the problem x - 1/y^2 = 0. So, given x, solve for y using an iterative scheme.

Y_(n+1) = y_n * (3 - x*y_n^2)/2

除以2只是一个位移，或者在最坏的情况下，乘以0.5.该方案完全按照要求收敛到y = 1/sqrt(x)，完全没有任何真除法.

The divide by 2 is just a bit shift, or at worst, a multiply by 0.5. This scheme converges to y=1/sqrt(x), exactly as requested, and without any true divides at all.

唯一的问题是您需要一个合适的y起始值.我记得在收敛的估计数y上有限制.

The only problem is that you need a decent starting value for y. As I recall there are limits on the estimate y for the iterations to converge.

这篇关于固定点的逆平方根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！