固定点的反平方

Question

我正在寻找固定点16.16数字的最佳逆平方根算法。到目前为止，下面的代码是我所拥有的（但是基本上，它取平方根并除以原始数，我想得到不除数的平方根倒数）。如果更改了任何内容，则将为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);
}

Answer 1

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

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

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

唯一的问题是你需要一个合适的 y 起始值。我记得迭代收敛的估计 y 是有限制的。