Dav*_*ica 5 java algorithm math square-root
如何有效地找到小于给定 int 的最大平方数(即 4、9、16)n
?我有以下尝试:
int square = (int)Math.sqrt(number);
return square*square;
Run Code Online (Sandbox Code Playgroud)
但它显然效率低下,无法获得平方根,以便我们可以对其进行平方。
前面:应该指出的是,能够将 sqrt 作为机器指令执行的处理器将足够快。毫无疑问,它的(微)程序使用了牛顿-拉夫森(Newton-Raphson)算法,并且该算法是二次收敛的,每次迭代的精确位数加倍。
因此,像这样的想法并不真正值得追求,尽管它们使用了正方形等的良好属性。(请参阅下一个提案)
// compute the root of the biggests square that is a power of two < n
public static int pcomp( int n ){
long p2 = 1;
int i = 0;
while( p2 < n ){
p2 <<= 2;
i += 2;
}
p2 >>= 2;
i -= 2;
return (int)(p2 >>= i/2);
}
public static int squareLowerThan( int n ){
int p = pcomp(n);
int p2 = p*p; // biggest power of two that is a square < n
int d = 1; // increase using odd numbers until n is exceeded
while( p2 + 2*p + d < n ){
p2 += 2*p + d;
d += 2;
}
return p2;
}
Run Code Online (Sandbox Code Playgroud)
但我确信牛顿算法更快。二次收敛,记住。
public static int sqrt( int n ){
int x = n;
while( true ){
int y = (x + n/x)/2;
if( y >= x ) return x;
x = y;
}
}
Run Code Online (Sandbox Code Playgroud)
这将返回整数平方根。返回 x*x 以获得 n 下面的平方。