math - 定点的逆平方

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 是有限制的。