l*********y
发帖数: 142 | 1 double mysqrt(double i)
{
if (i <= 0) return 0;
double low = 1, high = i;
if (i < 1) {
low = i;
high = 1;
}
int index = 0;
while (index < 64) {
double mid = low + (high - low) / 2;
if (mid * mid > i) {
high = mid;
} else {
low = mid;
}
index ++;
}
return low;
} |
c******w
发帖数: 102 | 2 if (mid * mid > i) {
high = mid;
} else {
low = mid;
}
这个地方可能出现溢出。 因为 double low = 1, high = i; 如果i的值本身比较大，
那么 mid*mide 的值很可能会比i的值大。 举个例子来说， 如果这个函数是求一个int
i的sqrt.假定 i= 2147483647， 那么你的mid值就会是 mid = low + (high - low) /
2 = 1073741823， 显然 1073741823* 1073741823的值比最大的int数要大多了。 类
似的问题也会发生到double类型上来。
比较好的办法是不是应该在初始化high的时候选择个适当大小的数字。 比如说 high =
1 << 32 如果是求double类型数字的sqrt。 |
b*******8
发帖数: 37364 | 3 first use bit right shift to estimate which [2^n, 2^(n+1)] interval the
integer is in. Then you get an pretty close interval [2^m, 2^(m+1)] the
squre root is in. Then binary search starts from this. |
l*********y
发帖数: 142 | 4
，
int
/
Thanks a lot for your suggestion!
How about the following?
double mysqrt(double i)
{
if (i <= 0) return 0;
double low = 1, high = i;
if (i < 1) {
low = i;
high = 1;
}
int index = 0;
while (index < 64) {
double mid = low + (high - low) / 2;
if (mid > i / mid) { // avoid mid * mid in the condition checking
high = mid;
} else {
low = mid;
}
index ++;
}
return low;
}
【在 c******w 的大作中提到】
: if (mid * mid > i) {
: high = mid;
: } else {
: low = mid;
: }
: 这个地方可能出现溢出。 因为 double low = 1, high = i; 如果i的值本身比较大，
: 那么 mid*mide 的值很可能会比i的值大。 举个例子来说， 如果这个函数是求一个int
: i的sqrt.假定 i= 2147483647， 那么你的mid值就会是 mid = low + (high - low) /
: 2 = 1073741823， 显然 1073741823* 1073741823的值比最大的int数要大多了。 类
: 似的问题也会发生到double类型上来。
|
f*****w
发帖数: 2602 | |
U*****R
发帖数: 60 | 6 为什么 用一个64次的循环，while (index < 64) ，
我觉得可以用 while(high－low 》 0.00000001) |
P***P
发帖数: 1387 | 7 google quake III inverse sqrt |
l*********y
发帖数: 142 | 8 double mysqrt(double i)
{
if (i <= 0) return 0;
double low = 1, high = i;
if (i < 1) {
low = i;
high = 1;
}
int index = 0;
while (index < 64) {
double mid = low + (high - low) / 2;
if (mid * mid > i) {
high = mid;
} else {
low = mid;
}
index ++;
}
return low;
} |
c******w
发帖数: 102 | 9 if (mid * mid > i) {
high = mid;
} else {
low = mid;
}
这个地方可能出现溢出。 因为 double low = 1, high = i; 如果i的值本身比较大，
那么 mid*mide 的值很可能会比i的值大。 举个例子来说， 如果这个函数是求一个int
i的sqrt.假定 i= 2147483647， 那么你的mid值就会是 mid = low + (high - low) /
2 = 1073741823， 显然 1073741823* 1073741823的值比最大的int数要大多了。 类
似的问题也会发生到double类型上来。
比较好的办法是不是应该在初始化high的时候选择个适当大小的数字。 比如说 high =
1 << 32 如果是求double类型数字的sqrt。 |
b*******8
发帖数: 37364 | 10 first use bit right shift to estimate which [2^n, 2^(n+1)] interval the
integer is in. Then you get an pretty close interval [2^m, 2^(m+1)] the
squre root is in. Then binary search starts from this. |
|
|
l*********y
发帖数: 142 | 11
，
int
/
Thanks a lot for your suggestion!
How about the following?
double mysqrt(double i)
{
if (i <= 0) return 0;
double low = 1, high = i;
if (i < 1) {
low = i;
high = 1;
}
int index = 0;
while (index < 64) {
double mid = low + (high - low) / 2;
if (mid > i / mid) { // avoid mid * mid in the condition checking
high = mid;
} else {
low = mid;
}
index ++;
}
return low;
}
【在 c******w 的大作中提到】
: if (mid * mid > i) {
: high = mid;
: } else {
: low = mid;
: }
: 这个地方可能出现溢出。 因为 double low = 1, high = i; 如果i的值本身比较大，
: 那么 mid*mide 的值很可能会比i的值大。 举个例子来说， 如果这个函数是求一个int
: i的sqrt.假定 i= 2147483647， 那么你的mid值就会是 mid = low + (high - low) /
: 2 = 1073741823， 显然 1073741823* 1073741823的值比最大的int数要大多了。 类
: 似的问题也会发生到double类型上来。
|
f*****w
发帖数: 2602 | |
U*****R
发帖数: 60 | 13 为什么 用一个64次的循环，while (index < 64) ，
我觉得可以用 while(high－low 》 0.00000001) |
P***P
发帖数: 1387 | 14 google quake III inverse sqrt |
m**q
发帖数: 189 | 15 这个64是怎么确定的? 有什么说法不
【在 l*********y 的大作中提到】
: double mysqrt(double i)
: {
: if (i <= 0) return 0;
: double low = 1, high = i;
: if (i < 1) {
: low = i;
: high = 1;
: }
: int index = 0;
: while (index < 64) {
|
f*******t
发帖数: 7549 | 16 float sqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point
bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can
be removed
return 1.0f / y;
} |
y*******g
发帖数: 6599 | 17 牛顿法的一个比较bt的初始值
【在 P***P 的大作中提到】
: google quake III inverse sqrt
|
m**q
发帖数: 189 | 18 lz的算法是二分不是牛顿法啊
我是没明白64次迭代有没有什么依据
【在 y*******g 的大作中提到】
: 牛顿法的一个比较bt的初始值
|
a********m
发帖数: 15480 | 19 卡马克这个bt。
【在 f*******t 的大作中提到】
: float sqrt( float number )
: {
: long i;
: float x2, y;
: const float threehalfs = 1.5F;
: x2 = number * 0.5F;
: y = number;
: i = * ( long * ) &y; // evil floating point
: bit level hacking
: i = 0x5f3759df - ( i >> 1 ); // what the fuck?
|
f*******t
发帖数: 7549 | 20 不是他写的
John Carmack, co-founder of id Software, is commonly associated with the
code, though he actually did not write it.
【在 a********m 的大作中提到】
: 卡马克这个bt。
|
a********m
发帖数: 15480 | 21 oh. 俺一直以为是it. 不过那时候id还是有不少bt的，可惜现在不行了。
【在 f*******t 的大作中提到】
: 不是他写的
: John Carmack, co-founder of id Software, is commonly associated with the
: code, though he actually did not write it.
|
f**l
发帖数: 44 | |
