该Math.sqrt()函数将双精度数作为参数并返回双精度数。我正在使用一个在所有情况下都使用完美方形网格的程序，我需要以整数形式获得平方根。这样做的唯一方法是将参数转换为 anint然后返回一个int-casted double 吗？
问问题
34095 次
4 回答
29
铸造技术比乍看起来要好得多。
从 int 到 double 的转换是准确的。
对于正常的正数，Math.sqrt 指定返回“最接近参数值的真正数学平方根的双精度值”。如果输入是完美平方 int，则结果将是 int 范围内的整数值 double。
同样，将该整数值 double 转换回 int 也是精确的。
最终效果是强制转换技术不会在您的情况下引入任何舍入误差。
如果您的程序可以从使用 Guava intMath API 中受益，您可以使用它来计算平方根，但我不会为了避免强制转换而添加对 API 的依赖。
于 2013-03-04T22:50:46.887 回答
10
您始终可以使用 Google Guava IntMath API。
final int sqrtX = IntMath.sqrt(x, RoundingMode.HALF_EVEN);
于 2013-03-04T22:41:51.707 回答
1
如果您只计算完美平方的平方根，您是否考虑过将它们预先计算到表格中的选项？整数完全平方的数量是有限的，大多数 JVM 可以毫不费力地同时保存所有这些。如果空间非常宝贵，我相信在这个方向上会有其他选择。
虽然有 65535 个，但如果这太多了，你可以存储四分之一，然后计算介于两者之间的那些。毕竟 (x+1)^2 = (x+1)(x+1) = x^2 + 2x + 1。
于 2013-03-04T22:57:25.340 回答
1
也许有人感兴趣，找到了一个链接：
http://atoms.alife.co.uk/sqrt/index.html
/*
ATOMS
Fast integer square roots in Java
Here are several fast integer square root methods, written in Java, including:
sqrt(x) agrees completely with (int)(java.lang.Math.sqrt(x)) for x < 2147483648 (i.e. 2^31), while executing about three times faster than it1.
fast_sqrt(x) agrees completely with (int)(java.lang.Math.sqrt(x)) for x < 289 (and provides a reasonable approximation thereafter), while executing about five times faster than it1.
SquareRoot.java - fast integer square root class;
SquareRootTest.java - basic speed and accuracy test class.
Thanks to Paul Hsieh's square root page for the accurate algorithm.
This code has been placed in the public domain.
Can you improve on the speed or accuracy of these methods (without chewing an "unreasonable" quantity of cache with a huge look-up table)?
If so, drop us a line, and hopefully we'll put your name up in lights.
[1: your mileage may vary]
tim@tt1.org | http://atoms.org.uk/
*/
/*
* Integer Square Root function
* Contributors include Arne Steinarson for the basic approximation idea, Dann
* Corbit and Mathew Hendry for the first cut at the algorithm, Lawrence Kirby
* for the rearrangement, improvments and range optimization, Paul Hsieh
* for the round-then-adjust idea, Tim Tyler, for the Java port
* and Jeff Lawson for a bug-fix and some code to improve accuracy.
*
*
* v0.02 - 2003/09/07
*/
/**
* Faster replacements for (int)(java.lang.Math.sqrt(integer))
*/
public class SquareRoot {
final static int[] table = {
0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53, 55, 57,
59, 61, 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83,
84, 86, 87, 89, 90, 91, 93, 94, 96, 97, 98, 99, 101, 102,
103, 104, 106, 107, 108, 109, 110, 112, 113, 114, 115, 116, 117, 118,
119, 120, 121, 122, 123, 124, 125, 126, 128, 128, 129, 130, 131, 132,
133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 144, 145,
146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155, 156, 157,
158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168,
169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178,
179, 180, 181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188,
189, 189, 190, 191, 192, 192, 193, 193, 194, 195, 195, 196, 197, 197,
198, 199, 199, 200, 201, 201, 202, 203, 203, 204, 204, 205, 206, 206,
207, 208, 208, 209, 209, 210, 211, 211, 212, 212, 213, 214, 214, 215,
215, 216, 217, 217, 218, 218, 219, 219, 220, 221, 221, 222, 222, 223,
224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230, 230, 231,
231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238,
239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246,
246, 247, 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253,
253, 254, 254, 255
};
/**
* A faster replacement for (int)(java.lang.Math.sqrt(x)). Completely accurate for x < 2147483648 (i.e. 2^31)...
*/
static int sqrt(int x) {
int xn;
if (x >= 0x10000) {
if (x >= 0x1000000) {
if (x >= 0x10000000) {
if (x >= 0x40000000) {
xn = table[x >> 24] << 8;
} else {
xn = table[x >> 22] << 7;
}
} else {
if (x >= 0x4000000) {
xn = table[x >> 20] << 6;
} else {
xn = table[x >> 18] << 5;
}
}
xn = (xn + 1 + (x / xn)) >> 1;
xn = (xn + 1 + (x / xn)) >> 1;
return ((xn * xn) > x) ? --xn : xn;
} else {
if (x >= 0x100000) {
if (x >= 0x400000) {
xn = table[x >> 16] << 4;
} else {
xn = table[x >> 14] << 3;
}
} else {
if (x >= 0x40000) {
xn = table[x >> 12] << 2;
} else {
xn = table[x >> 10] << 1;
}
}
xn = (xn + 1 + (x / xn)) >> 1;
return ((xn * xn) > x) ? --xn : xn;
}
} else {
if (x >= 0x100) {
if (x >= 0x1000) {
if (x >= 0x4000) {
xn = (table[x >> 8]) + 1;
} else {
xn = (table[x >> 6] >> 1) + 1;
}
} else {
if (x >= 0x400) {
xn = (table[x >> 4] >> 2) + 1;
} else {
xn = (table[x >> 2] >> 3) + 1;
}
}
return ((xn * xn) > x) ? --xn : xn;
} else {
if (x >= 0) {
return table[x] >> 4;
}
}
}
illegalArgument();
return -1;
}
/**
* A faster replacement for (int)(java.lang.Math.sqrt(x)). Completely accurate for x < 2147483648 (i.e. 2^31)...
* Adjusted to more closely approximate
* "(int)(java.lang.Math.sqrt(x) + 0.5)"
* by Jeff Lawson.
*/
static int accurateSqrt(int x) {
int xn;
if (x >= 0x10000) {
if (x >= 0x1000000) {
if (x >= 0x10000000) {
if (x >= 0x40000000) {
xn = table[x >> 24] << 8;
} else {
xn = table[x >> 22] << 7;
}
} else {
if (x >= 0x4000000) {
xn = table[x >> 20] << 6;
} else {
xn = table[x >> 18] << 5;
}
}
xn = (xn + 1 + (x / xn)) >> 1;
xn = (xn + 1 + (x / xn)) >> 1;
return adjustment(x, xn);
} else {
if (x >= 0x100000) {
if (x >= 0x400000) {
xn = table[x >> 16] << 4;
} else {
xn = table[x >> 14] << 3;
}
} else {
if (x >= 0x40000) {
xn = table[x >> 12] << 2;
} else {
xn = table[x >> 10] << 1;
}
}
xn = (xn + 1 + (x / xn)) >> 1;
return adjustment(x, xn);
}
} else {
if (x >= 0x100) {
if (x >= 0x1000) {
if (x >= 0x4000) {
xn = (table[x >> 8]) + 1;
} else {
xn = (table[x >> 6] >> 1) + 1;
}
} else {
if (x >= 0x400) {
xn = (table[x >> 4] >> 2) + 1;
} else {
xn = (table[x >> 2] >> 3) + 1;
}
}
return adjustment(x, xn);
} else {
if (x >= 0) {
return adjustment(x, table[x] >> 4);
}
}
}
illegalArgument();
return -1;
}
private static int adjustment(int x, int xn) {
// Added by Jeff Lawson:
// need to test:
// if |xn * xn - x| > |x - (xn-1) * (xn-1)| then xn-1 is more accurate
// if |xn * xn - x| > |(xn+1) * (xn+1) - x| then xn+1 is more accurate
// or, for all cases except x == 0:
// if |xn * xn - x| > x - xn * xn + 2 * xn - 1 then xn-1 is more accurate
// if |xn * xn - x| > xn * xn + 2 * xn + 1 - x then xn+1 is more accurate
int xn2 = xn * xn;
// |xn * xn - x|
int comparitor0 = xn2 - x;
if (comparitor0 < 0) {
comparitor0 = -comparitor0;
}
int twice_xn = xn << 1;
// |x - (xn-1) * (xn-1)|
int comparitor1 = x - xn2 + twice_xn - 1;
if (comparitor1 < 0) { // need to correct for x == 0 case?
comparitor1 = -comparitor1; // only gets here when x == 0
}
// |(xn+1) * (xn+1) - x|
int comparitor2 = xn2 + twice_xn + 1 - x;
if (comparitor0 > comparitor1) {
return (comparitor1 > comparitor2) ? ++xn : --xn;
}
return (comparitor0 > comparitor2) ? ++xn : xn;
}
/**
* A *much* faster replacement for (int)(java.lang.Math.sqrt(x)). Completely accurate for x < 289...
*/
static int fastSqrt(int x) {
if (x >= 0x10000) {
if (x >= 0x1000000) {
if (x >= 0x10000000) {
if (x >= 0x40000000) {
return (table[x >> 24] << 8);
} else {
return (table[x >> 22] << 7);
}
} else if (x >= 0x4000000) {
return (table[x >> 20] << 6);
} else {
return (table[x >> 18] << 5);
}
} else if (x >= 0x100000) {
if (x >= 0x400000) {
return (table[x >> 16] << 4);
} else {
return (table[x >> 14] << 3);
}
} else if (x >= 0x40000) {
return (table[x >> 12] << 2);
} else {
return (table[x >> 10] << 1);
}
} else if (x >= 0x100) {
if (x >= 0x1000) {
if (x >= 0x4000) {
return (table[x >> 8]);
} else {
return (table[x >> 6] >> 1);
}
} else if (x >= 0x400) {
return (table[x >> 4] >> 2);
} else {
return (table[x >> 2] >> 3);
}
} else if (x >= 0) {
return table[x] >> 4;
}
illegalArgument();
return -1;
}
private static void illegalArgument() {
throw new IllegalArgumentException("Attemt to take the square root of negative number");
}
/** From http://research.microsoft.com/~hollasch/cgindex/math/introot.html
* where it is presented by Ben Discoe (rodent@netcom.COM)
* Not terribly speedy...
*/
/*
static int unrolled_sqrt(int x) {
int v;
int t = 1<<30;
int r = 0;
int s;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;} t >>= 2;
s = t + r; r>>= 1;
if (s <= x) { x -= s; r |= t;}
return r;
}
*/
/**
* Mark Borgerding's algorithm...
* Not terribly speedy...
*/
/*
static int mborg_sqrt(int val) {
int guess=0;
int bit = 1 << 15;
do {
guess ^= bit;
// check to see if we can set this bit without going over sqrt(val)...
if (guess * guess > val )
guess ^= bit; // it was too much, unset the bit...
} while ((bit >>= 1) != 0);
return guess;
}
*/
/**
* Taken from http://www.jjj.de/isqrt.cc
* Code not tested well...
* Attributed to: http://www.tu-chemnitz.de/~arndt/joerg.html / email: arndt@physik.tu-chemnitz.de
* Slow.
*/
/*
final static int BITS = 32;
final static int NN = 0; // range: 0...BITSPERLONG/2
final static int test_sqrt(int x) {
int i;
int a = 0; // accumulator...
int e = 0; // trial product...
int r;
r=0; // remainder...
for (i=0; i < (BITS/2) + NN; i++)
{
r <<= 2;
r += (x >> (BITS - 2));
x <<= 2;
a <<= 1;
e = (a << 1)+1;
if(r >= e)
{
r -= e;
a++;
}
}
return a;
}
*/
/*
// Totally hopeless performance...
static int test_sqrt(int n) {
float r = 2.0F;
float s = 0.0F;
for(; r < (float)n / r; r *= 2.0F);
for(s = (r + (float)n / r) / 2.0F; r - s > 1.0F; s = (r + (float)n / r) / 2.0F) {
r = s;
}
return (int)s;
}
*/
}
/*
* Test Integer Square Root function
*/
public class SquareRootTest {
public static void main(String args[]) {
int x = -2;
debug("" + (x == -2L));
// perform timings...
//testSpeed();
// accuracy test...
testAccuracy();
// hang...
do {} while (true);
}
static void testSpeed() {
int i;
long newtime;
long oldtime;
int N = 10000000;
int mask = (1 << 16) - 1;
// SquareRoot.fast_sqrt()...
oldtime = System.currentTimeMillis();
for (i = 0; i < N; i++) {
int temp = SquareRoot.fastSqrt(i & mask);
}
newtime = System.currentTimeMillis();
debug("SquareRoot.fast_sqrt:" + (newtime - oldtime));
// SquareRoot.sqrt()...
oldtime = System.currentTimeMillis();
for (i = 0; i < N; i++) {
int temp = SquareRoot.sqrt(i & mask);
}
newtime = System.currentTimeMillis();
debug("SquareRoot.sqrt:" + (newtime - oldtime));
/*
// SquareRoot.mborg_sqrt()...
oldtime = System.currentTimeMillis();
for (i = 0; i < N; i++) {
temp = SquareRoot.mborg_sqrt(i & mask);
}
newtime = System.currentTimeMillis();
debug("SquareRoot.mborg_sqrt:" + (newtime - oldtime));
// SquareRoot.test_sqrt()...
oldtime = System.currentTimeMillis();
for (i = 0; i < N; i++) {
temp = SquareRoot.test_sqrt(i & mask);
}
newtime = System.currentTimeMillis();
debug("SquareRoot.test_sqrt:" + (newtime - oldtime));
*/
// java.lang.Math.sqrt()...
oldtime = System.currentTimeMillis();
for (i = 0; i < N; i++) {
int temp = (int) (java.lang.Math.sqrt(i & mask));
}
newtime = System.currentTimeMillis();
debug("java.lang.Math.sqrt:" + (newtime - oldtime));
}
static void testAccuracy() {
int i;
int a;
int b;
int c;
int d;
int e;
int start = 0;
int last_wrong_value = 0;
for (i = start; ; i++) {
a = (int) (java.lang.Math.sqrt(i));
b = (int) (java.lang.Math.sqrt(i) + 0.5);
c = SquareRoot.sqrt(i);
d = SquareRoot.fastSqrt(i);
e = SquareRoot.accurateSqrt(i);
// e = SquareRoot.mborg_sqrt(i);
// f = SquareRoot.test_sqrt(i);
if (b != e) {
//if (a > (last_wrong_value * 1.05)) { // don't print too many wrong values - just a sample...
last_wrong_value = a;
debug("N:" + i + " - Math.sqrt:" + a + " - Math.sqrt+:" + b + " - accurateSqrt:" + e + " - sqrt:" + c);
}
//}
}
}
final static void debug(String o) {
System.out.println(o);
}
}
; ;
于 2015-02-14T08:46:45.983 回答