快速整数平方根逼近

莫滕

我目前正在寻找一个非常快速的整数平方根近似值,其中 floor(sqrt(x)) <= veryFastIntegerSquareRoot(x) <= x

平方根例程用于计算素数,如果仅sqrt(x)检查小于或等于的值作为的除数,则质数很快x

我目前拥有的是Wikipedia的此功能,将其进行了一点点调整以使用64位整数。

因为我没有其他功能可与之进行比较(或更精确地说,该功能对我而言太精确了,而且可能要花费更多的时间才能比实际结果要高。)

野生撒尿

无循环/无跳跃(很好:几乎;-)牛顿-拉夫森:

/* static will allow inlining */
static unsigned usqrt4(unsigned val) {
    unsigned a, b;

    if (val < 2) return val; /* avoid div/0 */

    a = 1255;       /* starting point is relatively unimportant */

    b = val / a; a = (a+b) /2;
    b = val / a; a = (a+b) /2;
    b = val / a; a = (a+b) /2;
    b = val / a; a = (a+b) /2;

    return a;
}

对于64位int,您还需要一些步骤(我的猜测:6)

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章