查找小于 n 的最大平方数的算法
Algorithm to find the largest square number smaller than n
如何有效地找到小于给定整数 n
的最大平方数(即 4、9、16)?我有以下尝试:
int square = (int)Math.sqrt(number);
return square*square;
但它的效率很低,因为我们只能求平方根才可以求平方。
线性时间算法:
int largestSquare(int n) {
int i = 0;
while ((i+1)*(i+1) < n) {
++i;
}
return i*i;
}
预先:应该注意的是,能够将 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;
}
但我确信牛顿算法更快。二次收敛,记住。
public static int sqrt( int n ){
int x = n;
while( true ){
int y = (x + n/x)/2;
if( y >= x ) return x;
x = y;
}
}
这return是整数平方根。 return x*x 得到 n 下面的平方。
有一个求平方根的牛顿算法,你需要的是m^2而不是m,在给定的link
即使你想直接找平方而不是找m,我认为也不会比这更快。
这里是工作代码
public static int squareLessThanN(int N)
{
int x=N;
int y=(x+N/x)/2;
while(y<x)
{
x=y;
y=(x+N/x)/2;
}
return x*x;
}
但内置平方根似乎无论如何都更快。刚刚测量了两者的运行时间。
class Square{
public static void main(String[] args)
{
long startTime = System.currentTimeMillis();
System.out.println(squareLessThanN(149899437943L));
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println("Running time is "+totalTime);
startTime = System.currentTimeMillis();
System.out.println(normal(149899437943L));
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
System.out.println("Running time is "+totalTime);
}
public static long squareLessThanN(long N)
{
long x=N;
long y=(x+N/x)/2;
while(y<x)
{
x=y;
y=(x+N/x)/2;
}
return x*x;
}
public static long normal(long N)
{
long square = (long)Math.sqrt(N);
return square*square;
}
}
输出为
149899060224
Running time is 1
149899060224
Running time is 0
如何有效地找到小于给定整数 n
的最大平方数(即 4、9、16)?我有以下尝试:
int square = (int)Math.sqrt(number);
return square*square;
但它的效率很低,因为我们只能求平方根才可以求平方。
线性时间算法:
int largestSquare(int n) {
int i = 0;
while ((i+1)*(i+1) < n) {
++i;
}
return i*i;
}
预先:应该注意的是,能够将 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;
}
但我确信牛顿算法更快。二次收敛,记住。
public static int sqrt( int n ){
int x = n;
while( true ){
int y = (x + n/x)/2;
if( y >= x ) return x;
x = y;
}
}
这return是整数平方根。 return x*x 得到 n 下面的平方。
有一个求平方根的牛顿算法,你需要的是m^2而不是m,在给定的link
即使你想直接找平方而不是找m,我认为也不会比这更快。
这里是工作代码
public static int squareLessThanN(int N)
{
int x=N;
int y=(x+N/x)/2;
while(y<x)
{
x=y;
y=(x+N/x)/2;
}
return x*x;
}
但内置平方根似乎无论如何都更快。刚刚测量了两者的运行时间。
class Square{
public static void main(String[] args)
{
long startTime = System.currentTimeMillis();
System.out.println(squareLessThanN(149899437943L));
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println("Running time is "+totalTime);
startTime = System.currentTimeMillis();
System.out.println(normal(149899437943L));
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
System.out.println("Running time is "+totalTime);
}
public static long squareLessThanN(long N)
{
long x=N;
long y=(x+N/x)/2;
while(y<x)
{
x=y;
y=(x+N/x)/2;
}
return x*x;
}
public static long normal(long N)
{
long square = (long)Math.sqrt(N);
return square*square;
}
}
输出为
149899060224
Running time is 1
149899060224
Running time is 0