b***t
发帖数: 42 | 1 就问了 double pow(double a, int b);
下面是我给的code:
{
if (b==0) return 1;
if (b==1) return a;
int c = abs(b);
double results=pow(a,c/2);
results=results*results;
results=(c%2 ==0)?results:results*a;
if (b<0) return 1/results;
else return results;
}
得知悲剧，大家看看我的code有问题吗？多谢 |
d********t
发帖数: 9628 | 2 看题目跟machine learning有毛关系啊！
【在 b***t 的大作中提到】
: 就问了 double pow(double a, int b);
: 下面是我给的code:
: {
: if (b==0) return 1;
: if (b==1) return a;
: int c = abs(b);
: double results=pow(a,c/2);
: results=results*results;
: results=(c%2 ==0)?results:results*a;
: if (b<0) return 1/results;
|
H*****1
发帖数: 4815 | 3 a = 0 ?
【在 b***t 的大作中提到】
: 就问了 double pow(double a, int b);
: 下面是我给的code:
: {
: if (b==0) return 1;
: if (b==1) return a;
: int c = abs(b);
: double results=pow(a,c/2);
: results=results*results;
: results=(c%2 ==0)?results:results*a;
: if (b<0) return 1/results;
|
q****x
发帖数: 7404 | 4 不简洁。
{
if (b==0) return 1;
if (b==1) return a;
int c = abs(b);
double results=pow(a,c/2);
results = results * results;
if (c%2) results *= a;
return (b < 0 ? 1/results : results);
}
递归也不是最高效的做法。循环好。
abs被递归函数调用多次。但其实一次就够。
另外0的0次方怎么算？
【在 b***t 的大作中提到】
: 就问了 double pow(double a, int b);
: 下面是我给的code:
: {
: if (b==0) return 1;
: if (b==1) return a;
: int c = abs(b);
: double results=pow(a,c/2);
: results=results*results;
: results=(c%2 ==0)?results:results*a;
: if (b<0) return 1/results;
|
P**********c
发帖数: 3417 | 5 我觉得简洁性和递归都还好。a=0那个情况考虑不到的人应该也很多。如果只有这一道
题的话，应该是解题过程问题。如果楼主是一下子得出答案的，那不太可能就这一题。
如果整个电面就解了这一题，那过程肯定不短。
【在 q****x 的大作中提到】
: 不简洁。
: {
: if (b==0) return 1;
: if (b==1) return a;
: int c = abs(b);
: double results=pow(a,c/2);
: results = results * results;
: if (c%2) results *= a;
: return (b < 0 ? 1/results : results);
: }
|
q****x
发帖数: 7404 | 6 同意。
【在 P**********c 的大作中提到】
: 我觉得简洁性和递归都还好。a=0那个情况考虑不到的人应该也很多。如果只有这一道
: 题的话，应该是解题过程问题。如果楼主是一下子得出答案的，那不太可能就这一题。
: 如果整个电面就解了这一题，那过程肯定不短。
|
B*******1
发帖数: 2454 | 7 上个我收藏的火鸡的代码：
public double power(double x, int n) {
if (n < 0) return 1.0/power(x, -n);
double r = 1.0, pow = x;
while (n > 0) {
if ( (1 & n) > 0 ) r *= pow;
n >>= 1;
pow *= pow;
}
return r;
} |
f*******t
发帖数: 7549 | 8 练习时写的，开方数支持小数和负数
double sqrt(double n)
{
if(n <= 0.0)
return 0.0;
double ans = n / 2.0;
int round = 0;
const double epsilon = 0.00001;
while(true) {
round++;
ans = (ans + n / ans) / 2;
double diff = ans * ans - n;
if(diff < 0)
diff = -diff;
if(diff < epsilon)
break;
}
//printf("Calculated %d rounds\n", round);
return ans;
}
double powerDouble(double a, double n) {
bool neg = false;
if(n < 0.0) {
neg = true;
n = -n;
}
double result = 1.0;
double part1 = a, part2 = sqrt(a);
int nl = (int)n;
double nr = n - (double)nl;
printf("n = %f, left = %ld, right = %f\n", n, nl, nr);
while(nl > 0) {
if(nl & 1)
result *= part1;
part1 *= part1;
nl >>= 1;
}
nr *= 2.0;
int count = 0;
while(nr > 0.0) {
if(nr >= 1.0) {
result *= part2;
nr -= 1.0;
}
part2 = sqrt(part2);
nr *= 2.0;
count++;
if(count > 10)
break;
}
if(neg)
return 1.0 / result;
else
return result;
} |
q****x
发帖数: 7404 | 9 n > 1 vs n < 1?
【在 f*******t 的大作中提到】
: 练习时写的，开方数支持小数和负数
: double sqrt(double n)
: {
: if(n <= 0.0)
: return 0.0;
:
: double ans = n / 2.0;
: int round = 0;
: const double epsilon = 0.00001;
: while(true) {
|
x*****o
发帖数: 23 | 10 仰慕。。。
【在 f*******t 的大作中提到】
: 练习时写的，开方数支持小数和负数
: double sqrt(double n)
: {
: if(n <= 0.0)
: return 0.0;
:
: double ans = n / 2.0;
: int round = 0;
: const double epsilon = 0.00001;
: while(true) {
|
|
|
f*******t
发帖数: 7549 | 11 ?
【在 q****x 的大作中提到】
: n > 1 vs n < 1?
|
q****x
发帖数: 7404 | 12 原来是牛顿法。
【在 f*******t 的大作中提到】
: ?
|
i*o
发帖数: 149 | 13 Because double (similarly float) only has limited precision, the
associative
law for multiplication does not hold.
In other words, following equation is NOT true for double.
a*a*a*a = (a*a)*(a*a)
The rounding error could become significant enough that two will have
different results.
For the same reason, many compile optimizations are not performed for
equations involving double and floating. |
r****t
发帖数: 10904 | 14 certainly right. But then how to solve this problem?
【在 i*o 的大作中提到】
: Because double (similarly float) only has limited precision, the
: associative
: law for multiplication does not hold.
: In other words, following equation is NOT true for double.
: a*a*a*a = (a*a)*(a*a)
: The rounding error could become significant enough that two will have
: different results.
: For the same reason, many compile optimizations are not performed for
: equations involving double and floating.
|
H***e
发帖数: 476 | 15 我觉得逻辑上来说，iterative的没有recursive的intuitive,为什么大家逗这么喜欢
iterative呢
【在 B*******1 的大作中提到】
: 上个我收藏的火鸡的代码：
: public double power(double x, int n) {
: if (n < 0) return 1.0/power(x, -n);
: double r = 1.0, pow = x;
: while (n > 0) {
: if ( (1 & n) > 0 ) r *= pow;
: n >>= 1;
: pow *= pow;
: }
: return r;
|
A*********c
发帖数: 430 | 16 因为iterative没有recursive的stack overhead。
【在 H***e 的大作中提到】
: 我觉得逻辑上来说，iterative的没有recursive的intuitive,为什么大家逗这么喜欢
: iterative呢
|
n*****n
发帖数: 1029 | 17 上面有几位问a=0的情况，这不算special case，完全不用单独考虑，因为0^0=1。
另外，这题应该考虑到overflow如何处理，这是这类题经常考察的一点。
【在 b***t 的大作中提到】
: 就问了 double pow(double a, int b);
: 下面是我给的code:
: {
: if (b==0) return 1;
: if (b==1) return a;
: int c = abs(b);
: double results=pow(a,c/2);
: results=results*results;
: results=(c%2 ==0)?results:results*a;
: if (b<0) return 1/results;
|
d****o
发帖数: 1055 | 18 那这道题怎么做？
double的最大值。。。
【在 n*****n 的大作中提到】
: 上面有几位问a=0的情况，这不算special case，完全不用单独考虑，因为0^0=1。
: 另外，这题应该考虑到overflow如何处理，这是这类题经常考察的一点。
|
m******t
发帖数: 6905 | |
q****x
发帖数: 7404 | 20 google newton method
【在 H***e 的大作中提到】
: 我觉得逻辑上来说，iterative的没有recursive的intuitive,为什么大家逗这么喜欢
: iterative呢
|
|
|
H***e
发帖数: 476 | 21 嗯
看错了
【在 q****x 的大作中提到】
: google newton method
|
H***e
发帖数: 476 | 22 double diff = ans * ans - n;
这个还是可能超出Double.Max的范围的吧？
【在 f*******t 的大作中提到】
: 练习时写的，开方数支持小数和负数
: double sqrt(double n)
: {
: if(n <= 0.0)
: return 0.0;
:
: double ans = n / 2.0;
: int round = 0;
: const double epsilon = 0.00001;
: while(true) {
|
b******t
发帖数: 965 | 23 floating point的这些越界就不用太管了 不然code写起来太恶心了
【在 H***e 的大作中提到】
: double diff = ans * ans - n;
: 这个还是可能超出Double.Max的范围的吧？
|
w**z
发帖数: 8232 | 24 我孤陋寡闻，谁想出来的：
(ans + n/ans) /2
要是在面试时，能当场写出这个，如果没见过？如果见过的话，回答出来也没有多大意
义了。面试官也不傻。
实在不觉的这有啥好写的。Java math lib has the implementation of sqrt, 干嘛要
自己写？
要考你越界处理？研究这样的题，说实话对工作有啥帮助？
【在 f*******t 的大作中提到】
: 练习时写的，开方数支持小数和负数
: double sqrt(double n)
: {
: if(n <= 0.0)
: return 0.0;
:
: double ans = n / 2.0;
: int round = 0;
: const double epsilon = 0.00001;
: while(true) {
|
b******t
发帖数: 965 | 25 en 其实是看知识面
这个是数值算法
比如还有用+ - *来实现 /
通常可以会用逐位相减来做
也可以用newton法来做
【在 w**z 的大作中提到】
: 我孤陋寡闻，谁想出来的：
: (ans + n/ans) /2
: 要是在面试时，能当场写出这个，如果没见过？如果见过的话，回答出来也没有多大意
: 义了。面试官也不傻。
: 实在不觉的这有啥好写的。Java math lib has the implementation of sqrt, 干嘛要
: 自己写？
: 要考你越界处理？研究这样的题，说实话对工作有啥帮助？
|
f*******t
发帖数: 7549 | 26 反正这是面试时可能会考到的题，你是准备还是不准备呢？
【在 w**z 的大作中提到】
: 我孤陋寡闻，谁想出来的：
: (ans + n/ans) /2
: 要是在面试时，能当场写出这个，如果没见过？如果见过的话，回答出来也没有多大意
: 义了。面试官也不傻。
: 实在不觉的这有啥好写的。Java math lib has the implementation of sqrt, 干嘛要
: 自己写？
: 要考你越界处理？研究这样的题，说实话对工作有啥帮助？
|
w**z
发帖数: 8232 | 27 http://stackoverflow.com/questions/825221/where-can-i-find-the-
It's a math problem more than CS. Well, don't know how far you want to go..
That is the implementation from math lib
public static double sqrt(double a) {
return StrictMath.sqrt(a); // default impl. delegates to StrictMath
// Note that hardware sqrt instructions
// frequently can be directly used by JITs
// and should be much faster than doing
// Math.sqrt in software.
}
The class StrictMath contains methods for performing basic numeric
operations such as the elementary exponential, logarithm, square root, and
trigonometric functions.
To help ensure portability of Java programs, the definitions of some of the
numeric functions in this package require that they produce the same results
as certain published algorithms. These algorithms are available from the
well-known network library netlib as the package "Freely Distributable Math
Library," fdlibm. These algorithms, which are written in the C programming
language, are then to be understood as executed with all floating-point
operations following the rules of Java floating-point arithmetic.
The Java math library is defined with respect to fdlibm version 5.3. Where
fdlibm provides more than one definition for a function (such as acos), use
the "IEEE 754 core function" version (residing in a file whose name begins
with the letter e). The methods which require fdlibm semantics are sin, cos,
tan, asin, acos, atan, exp, log, log10, cbrt, atan2, pow, sinh, cosh, tanh,
hypot, expm1, and log1p.
So by finding the appropriate version of the fdlibm source, you should also
find the exact implementation used by Java (and mandated by the
specification here).
The implementation used by fdlibm is
static const double one = 1.0, tiny=1.0e-300;
double z;
int sign = (int)0x80000000;
unsigned r,t1,s1,ix1,q1;
int ix0,s0,q,m,t,i;
ix0 = __HI(x); /* high word of x */
ix1 = __LO(x); /* low word of x */
/* take care of Inf and NaN */
if((ix0&0x7ff00000)==0x7ff00000) {
return x*x+x; /* sqrt(NaN)=NaN, sqrt(+inf)=+inf
sqrt(-inf)=sNaN */
}
/* take care of zero */
if(ix0<=0) {
if(((ix0&(~sign))|ix1)==0) return x;/* sqrt(+-0) = +-0 */
else if(ix0<0)
return (x-x)/(x-x); /* sqrt(-ve) = sNaN */
}
/* normalize x */
m = (ix0>>20);
if(m==0) { /* subnormal x */
while(ix0==0) {
m -= 21;
ix0 |= (ix1>>11); ix1 <<= 21;
}
for(i=0;(ix0&0x00100000)==0;i++) ix0<<=1;
m -= i-1;
ix0 |= (ix1>>(32-i));
ix1 <<= i;
}
m -= 1023; /* unbias exponent */
ix0 = (ix0&0x000fffff)|0x00100000;
if(m&1){ /* odd m, double x to make it even */
ix0 += ix0 + ((ix1&sign)>>31);
ix1 += ix1;
}
m >>= 1; /* m = [m/2] */
/* generate sqrt(x) bit by bit */
ix0 += ix0 + ((ix1&sign)>>31);
ix1 += ix1;
q = q1 = s0 = s1 = 0; /* [q,q1] = sqrt(x) */
r = 0x00200000; /* r = moving bit from right to left */
while(r!=0) {
t = s0+r;
if(t<=ix0) {
s0 = t+r;
ix0 -= t;
q += r;
}
ix0 += ix0 + ((ix1&sign)>>31);
ix1 += ix1;
r>>=1;
}
r = sign;
while(r!=0) {
t1 = s1+r;
t = s0;
if((t
s1 = t1+r;
if(((t1&sign)==sign)&&(s1&sign)==0) s0 += 1;
ix0 -= t;
if (ix1 < t1) ix0 -= 1;
ix1 -= t1;
q1 += r;
}
ix0 += ix0 + ((ix1&sign)>>31);
ix1 += ix1;
r>>=1;
}
/* use floating add to find out rounding direction */
if((ix0|ix1)!=0) {
z = one-tiny; /* trigger inexact flag */
if (z>=one) {
z = one+tiny;
if (q1==(unsigned)0xffffffff) { q1=0; q += 1;}
else if (z>one) {
if (q1==(unsigned)0xfffffffe) q+=1;
q1+=2;
} else
q1 += (q1&1);
}
}
ix0 = (q>>1)+0x3fe00000;
ix1 = q1>>1;
if ((q&1)==1) ix1 |= sign;
ix0 += (m <<20);
__HI(z) = ix0;
__LO(z) = ix1;
return z; |
g*******n
发帖数: 214 | 28 Mark
★ Sent from iPhone App: iReader Mitbbs Lite 7.39 |
z****c
发帖数: 602 | 29 试试写的短点。
double pow(double a, double b)
{
assert(a>0);
double result = 1.0;
if(b==0.0)
reutrn 1.0;
else if(b<0)
return pow(a,-b);
while(b > 0 && a > 0.000000001）
{
if(b>1)
{
result *= a;
b -= 1.0;
}
else if(b*2>1)
{
a = sqrt(a);
result *= a;
b = b*2 -1;
}
else
{
a = sqrt(a);
b *= 2;
}
}
return result;
} |
