F一题：double sqrt如何优化# JobHunting - 待字闺中
S*n
1 楼
binary search的话复杂度是log(nm), e= 10^-m;这个有办法优化吗？不知道面试官要
什么样的答案
什么样的答案
s*s
2 楼
newton法不能用在double上？
r*h
3 楼
double sqrt是说输入输出都要是double吗？
那应该用牛顿法比较好吧？
【在 S******n 的大作中提到】
: binary search的话复杂度是log(nm), e= 10^-m;这个有办法优化吗？不知道面试官要
: 什么样的答案
那应该用牛顿法比较好吧？
【在 S******n 的大作中提到】
: binary search的话复杂度是log(nm), e= 10^-m;这个有办法优化吗？不知道面试官要
: 什么样的答案
S*n
4 楼
就一直问我怎样优化，没说要用牛顿法啊，他就说如果x很大或者很小的情况下，应该
如何处理
如何处理
c*p
5 楼
还能再优化么？我想想。。。
c*y
6 楼
很小的时候，1/sqrt(1/x) 等价于很大
x很大的时候，可以把初始值猜得小一点。 肯定排除二分，起码newton-raphson
【在 S******n 的大作中提到】
: 就一直问我怎样优化，没说要用牛顿法啊，他就说如果x很大或者很小的情况下，应该
: 如何处理
x很大的时候，可以把初始值猜得小一点。 肯定排除二分，起码newton-raphson
【在 S******n 的大作中提到】
: 就一直问我怎样优化，没说要用牛顿法啊，他就说如果x很大或者很小的情况下，应该
: 如何处理
c*a
7 楼
newton就是优化。你画一画就明白了，比2分缩得还快。
在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。
在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。
r*h
8 楼
嗯，如果不用牛顿法，至少也要gradient descent
【在 c******a 的大作中提到】
: newton就是优化。你画一画就明白了，比2分缩得还快。
: 在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。
【在 c******a 的大作中提到】
: newton就是优化。你画一画就明白了，比2分缩得还快。
: 在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。
x*0
9 楼
mark
g*s
10 楼
不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
【在 c******a 的大作中提到】
: newton就是优化。你画一画就明白了，比2分缩得还快。
: 在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。
【在 c******a 的大作中提到】
: newton就是优化。你画一画就明白了，比2分缩得还快。
: 在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。
l*t
11 楼
牛顿本质上就是线性逼近
理解这个现场推公式还是不难的
【在 g*******s 的大作中提到】
: 不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
理解这个现场推公式还是不难的
【在 g*******s 的大作中提到】
: 不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
c*a
12 楼
只要以前看过一遍，一辈子都记住了吧。。。。。
【在 g*******s 的大作中提到】
: 不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
【在 g*******s 的大作中提到】
: 不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
s*s
13 楼
//agree. 我碰到过求三次方的，楞了一下，然后就推出来了。interviewer很高兴。
【在 c******a 的大作中提到】
: 只要以前看过一遍，一辈子都记住了吧。。。。。
【在 c******a 的大作中提到】
: 只要以前看过一遍，一辈子都记住了吧。。。。。
c*p
14 楼
先mark
r*h
15 楼
记住
x_1 = x_0 - f(x_0)/f'(x_0) 就可以啦
【在 g*******s 的大作中提到】
: 不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
x_1 = x_0 - f(x_0)/f'(x_0) 就可以啦
【在 g*******s 的大作中提到】
: 不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
p*e
16 楼
加上这个？
double power = 1.;
while(x < 1.){
power /= 10.;
x *= 100;
}
while(x > 100.){
power *= 10.;
x /= 100.;
}
.....
return ret*power;
【在 S******n 的大作中提到】
: 就一直问我怎样优化，没说要用牛顿法啊，他就说如果x很大或者很小的情况下，应该
: 如何处理
double power = 1.;
while(x < 1.){
power /= 10.;
x *= 100;
}
while(x > 100.){
power *= 10.;
x /= 100.;
}
.....
return ret*power;
【在 S******n 的大作中提到】
: 就一直问我怎样优化，没说要用牛顿法啊，他就说如果x很大或者很小的情况下，应该
: 如何处理
相关阅读
说个icc的名字叫做cyberthink，这个公司怎么样？[Apple Openings] Driver, GPU, graphics, algorithms请教大家一个小问题求推荐wall street工作的head hunters问一个题 house paint提供内部refer，网络公司，地点bothsell，离西雅图20分钟到现在还不明白么？美国是以族裔为单位竞争利益 (转载)有接wechat app 开发的吗？如果要找现公司match，最好是什么时机？Comcast opening in bay area器件物理方面哪些公司有机会？求CAREER定位CS专业小妹跪求内推！！！！non-competition 到底怎么确定？【请教】个关于H4身份工作读书的问题人家阿三印度理工很重视presentation的！ (转载)紧急求助 南新泽西 vs 北卡全美华人职业互助从两件小事做起 (转载)VMware vs Apple印度阿三即将占领中国职场 (转载)版上大牛们说说ads还有前途吗