一道程序猿面试题目, 大家来看看?

牛顿迭代，这题面试要出不分分钟秒掉……

两个思路，一是二分法逼近，二是牛顿法

这个不就是二分法求解吗？牛顿迭代法迭代的次数可以更少，但是记得是不能根据任意的 elision 值来求值的。

第一反应就是牛顿法, 这个比较考数学功底了吧, Leetcode 上有个基本一致的题

这个不是数学题吗

牛顿法

SICP 里面就有一个这样的例子，不过是用 Lisp 写的就是了

看来 V 站的程序猿素质高些, 哈哈. 我也认为 2 分(至少经过提示后), 应该能写出来才对. 不过实际面试过程中, 很难有人写出来. 题目就是 leetcode 上原题稍微变动加了个约束条件.

说归说, 能 show me your code 试试吗?

用牛顿法，公式已经忘记了，初始值远取很重要。 http://diducoder.com/sotry-about-sqrt.html

牛顿迭代+1
误差通过证明误差收敛的公式分析(这里需要知道部分变量的准确的函数值，才能给出误差的上界)
sqrt.c(apple)的实际做法是把估计值列举出来，存储在数组中，然后再用牛顿迭代计算：
https://opensource.apple.com/source/Libm/Libm-92/ppc.subproj/sqrt.c

函数式编程 用 fixed point 来解
参考资料 https://briangordon.github.io/2014/06/sqrts-and-fixed-points.html

看到题目，不借助搜索引擎的情况下能想到牛顿法，但具体到代码上估计还是得查一下…

'''
function sqrt(num, ep) {
let step = (cb) => {
return (a,v) => {
let x = (v + a / v) / 2,
d = Math.abs(a - x*x);
if (d < ep) return x;
return cb(a, x);
};
};

let Z = (f) => ((x) => f((v1, v2) => x(x)(v1, v2)))(x => f((v1, v2) => x(x)(v1, v2)));

return Z(step)(num, num/2);
}

console.log(sqrt(9,0.21));
'''

变量 xjb 命名，函数 xjb 创建，凑凑活活写出来了。
https://oi46s5f95.qnssl.com/[email protected]
@tl3shi

同感，这不数学题吗，哈哈。数值计算虽然经常被用到软件中，但它毕竟是用数学手段去解决数学问题。

Newton Iterative Sqrt Method https://helloacm.com/newton-iterative-sqrt-method/

道理我都懂，可是对 v 对开根号， t 是干嘛用的？

@ivanlw 最大误差。

sqrt = ->(sq, t) { rt = sq * 1.0; rt = (rt + sq / rt) / 2 while (rt * rt - sq).abs >= (t * t); rt }
sqrt.call(9, 0.21)
# => 3.00009155413138
sqrt.call(9, 0.0001)
# => 3.000000001396984

@ivanlw t 是误差，计算机开根号 也只能求解近似值

上面的解法好像改变了精度了。

按照原题要求的精度来的话，牛顿迭代和二分法的 Ruby 实现：
test = ->(sq, t, rt) { (rt+t) * (rt+t) < sq || (rt-t) * (rt-t) > sq }
sqrt1 = ->(sq, t) { rt = sq * 1.0; rt = (rt + sq / rt) / 2 while test.call(sq, t, rt); rt }
sqrt2 = ->(sq, t) { (0..sq.to_f).bsearch { |rt| test.call(sq, t, rt) ? sq - rt * rt : 0 } }

sqrt1.call(9, 0.21)
# => 3.023529411764706
sqrt1.call(9, 0.0001)
# => 3.00009155413138

sqrt2.call(9, 0.21)
# => 2.993255615234375
sqrt2.call(9, 0.0001)
# => 2.9999834150075912

如果让我面试做这种狗屎题，我心里肯定会说，
你这套路不对，这题我平时刷的时候没怎么见过，
面试时间一般也就 20 分钟-1 小时
这还要人编写正确的程序出来，还不给上网查资料，
这么简单的题目，写错了就没分，我操，面试官 傻逼 脑残 负分 滚出
为什么说这题简单呢？因为这题 一看就是烂大街的题目 我要是做不出来 不就负分了么
（虽然我能把二分整数搜索的算法记忆的滚瓜烂熟）

public static double sqrt(int v, double t) {
assert (v > 0 && t > 0);
double lo = 0.0, hi = v * 1.0;
while (lo < hi) {
double mid = lo + (hi - lo) / 2;
double midSq = mid * mid;
double diff = (midSq - v) >= 0 ? (midSq - v) : (v - midSq);
if (diff <= t)
return mid;
if (midSq > v)
hi = mid;
else
lo = mid;
}
return -1.0;
}

现在让我来说为什么这题是狗屎题了吧

让我解的话，只能想到一种办法 ，那就是根据 t 的精度进行 暴力搜索
每次只加 0.0000001 （假设） 直到 条件不满足的时候，那么前一个解 必然是在区间范围内的

这样一来，想到什么了没有，被我们暴力搜索的候选结果集 是一个等差数列
既然是等差数列，那么就是有序候选集，搜索有序结果集 必然采用我大 二分搜索法 能大大降低算法复杂度

关键是你 TM 的这公式，让我根本想不出这 二分搜索 递归结束的条件啊
（我们平常用二分搜索 都是搜索 整数 递归的结束条件 比较简单 ）

所以呢？

面试的时候，如果面试者讲暴力搜索，面试官心里面会想 这么暴力？连二分都不会

面试者心里想，什么狗屎题，老子也知道这题二分是能解的，但是你这破公式，我就是想不出 一个递归检索的条件

@kingdaa
你这错了 我瞄一眼 就知道你这错了，
面试你这样写 直接负分滚出，题意都没看懂

所以这题在没有其他数学功底等套路的情况下，
最多只能想到二分搜索，但是这题 难点并不在二分搜索本身，而在于从公式中(*ω)推导出结束条件，
结束条件，刷过这个题的人，肯定会心一笑，正好踩到面试官的点
没刷过这个题的人，心里就骂娘了

如果你真要考察 对二分搜索的应用能力，我建议出一个题目
讲一个故事 需要应用到 3sum ，要求算法复杂度低于 O(n3) ，即可
你这题目，面试者很难 get 到结束条件

这题解法太多了，之前网上看到过一篇文章，对比了 13 种不同的解法

方法很多，最常见就是牛顿迭代法。收敛比较快

出题人有数值分析的基础吗？……

```lisp
;Newton's method 二次开方
(define (sqrt x)
(define (sqrt-iter guess x)
(cond ((< (abs (- x (* guess guess))) 0.001 ) guess)
(else (sqrt-iter (improve guess x) x))
))
(define (improve guess x)
(/ (+ guess (/ x guess)) 2))
(define (abs x)
(if (< x 0)
(- x)
x))
(sqrt-iter 1.0 x))

(sqrt 4)
```

还记得以前看过一个开平方的神奇常数，用一个常数值作为起始猜值进行迭代，收敛会特别快

我想强调的不是说这道题目本身 而是说当有人给你一种思路后、能否在一步一步引导情况下思考并解决问题，最后能否将已经明白的思路变成实实在在的 code ，这肯定是较好的程序员应该具备的能力。

二分就是期待的答案，然而事实上就是并没有多少人写出。 结束条件就是一个坑给刷过这道题的人埋的，没刷过的人期望是经过提示后能写出二分。

楼上的代码貌似有不少是满足不了题意的

想到了当年 POJ 上面的一道打表题。。

@Cabana 是 0x5f375a86

贴一段神奇的代码，据说比编译器的开方函数还快 5 倍
```
float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x; // get bits for floating VALUE
i = 0x5f375a86- (i>>1); // gives initial guess y0
x = *(float*)&i; // convert bits BACK to float
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
return x;
}
```

没有用到系统库函数啊 ：）
```
double h_sqrt(int v, double t) {
double vd = (double)v;
double sqrt;
asm ("sqrtsd %1, %0"
: "=x" (sqrt)
: "xm" (vd));
return sqrt;
}
```

牛顿迭代法，没有查资料写的
https://gist.github.com/metowolf/859e9d1b116b55c553c828ff1b99bd3e

我想到平方根倒数快速算法，基于牛顿法，是雷神 3 里的一段代码，有对应 64 位的魔法数，也有误差分析，最后取倒数行不？

https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95

计算机程序的构造和解释中有非常详细的分析，由牛顿迭代法到最后抽象出的不动点搜寻，可以解决许多问题，比如求方程的根，求 PI 的值这种类型。

def simple_sqrt(v, t):
if v < 0:
raise ValueError('domain error')

if v == 0:
return 0

# binary search
if v < 1:
left, right = v, 1
else:
left, right = 0, v
while True:
mid = (left + right) / 2.0
dest = mid * mid
diff = dest - v

if diff > 0 and (mid - t) * (mid - t) <= v:
return mid
if diff < 0 and (mid + t) * (mid + t) >= v:
return mid
if diff == 0:
return mid

if diff > 0:
right = mid
else:
left = mid

这位 @q397064399 是何方神圣....

@xiamx 菜鸟一枚

这道题我不做

# Python
def sqrt(num, deli):
val_min = num - deli
val_max = num + deli
point = 1
while 1:
lower, bigger = [point, num] if num > point else [num, point]
mid = (lower + bigger)/2
tmp = mid ** 2
if tmp < val_min:
point, num = mid, bigger
num = bigger
elif tmp > val_max:
point, num = lower, mid
elif val_min < tmp < val_max:
return mid

print(sqrt(16, 0.21)) # 3.98828125

@tl3shi 二分法是你期待的答案。
但二分法并不是一个好的答案。牛顿迭代法的收敛速度比二分法快很多。
这道题的重点不是怎么算出平方根（方法有很多），而是做误差分析。如果需要严格地证明误差小于一定的值，首先必须要有已知的参考值。所以要有数据类型允许的范围内一系列已知的答案才能完整地解这道题。
ls 给出了各种方法，都被你否认；虽然也没有考虑误差的问题，但你也没仔细想过。
总的来说，你不是来问问题的，你想表达的就是：“我说的就是对的，其他都是垃圾。”

func sqrt(_ num: Double, precision: Double) -> Double {
var start = 0.0
var end = num
while (end - start) > precision {
let middle = (start + end) / 2
if middle * middle > num {
end = middle
} else {
start = middle
}
}

return (start + end) / 2
}

我水的掉渣。。。。。。

@q397064399 二分想不出结束条件完全是水平不行而已，和数学功底或者刷没刷过这个题有什么关系，只要会二分，结束条件都是显而易见的。倒是牛顿法的话结束条件难以判断一些

@nbndco 跪求所谓显而易见的结束条件 谢谢

@nbndco 同求，谢谢。

......热身算法题难度呀，这种题面 MFG 都要求直接秒的

@q397064399 区间的大小小于要求误差的时候取中值

题主的本意是，
通过一些不那么一眼就能看出来的题目 来检测一个人对教科书上的基本算法应用能力，
你们又是 牛顿迭代 又是啥的，明显是刷过题 知道各种套路老司机 何必来这里折腾，

这题的坑 楼主自己都说了，用二分搜索 结束条件 是新司机一下子想不到的，
何况这是个面试， 20 分钟-30 分钟的样子，能把二分写对，然后还要写测试，

@nbndco show code 吧， 不打嘴炮了，请问如何计算 你所谓的区间大小

签名都是错的，大把大把的 (v, t) 都可以让二分搜索永远停不了机。

@debiann 能写出牛顿迭代或者仅仅这种方法当然有好的印象加分， **看中的是在交流过程中思考解决问题的能力， 不是说这道题目写出来就 NB ， 写不出来就滚蛋**。


还有其他一些喷子， 麻烦好好看看原文好么。。。

http://mp.weixin.qq.com/s/0PsaOCR2k566SD9bRtgmlg

你们使劲喷吧， 让喷子来得更猛一些 喷之前， 求看完原文， 及想强调的东西。

我也当做自己在吃瓜 :)

不过， 可能题目文字上面描述得还可以更好。。。 对于某些人来说是比较排斥看什么公式的。

直接用循环控制二分次数。。。精度妥妥达到要求。。。

对于看过 SICP 的来说很简单吧。书上列题啊。

@tl3shi
第一，这个帖子里我没看见有“喷子”，只看到了你对回复者的不屑。
第二，牛顿迭代法并不是什么厉害的算法，这是计算方法的送分题。只要考试及格的人都会。

@q397064399 想不到的应该算是新手了，这么简单的题你要是非要胡搅蛮缠那你当我不会好了。这个题在我看来，二分基本算是白送，不需要任何前置知识，如果考虑到 double 表示的精度加点分，这个都不会还说会二分太逗了吧。
牛顿法本来就没要求，只不过这个题是有一个更好的解法，面试官又没要你会。事实上面试官希望你用二分，因为牛顿法其实是不好判断精度的。

@nbndco 你有时间打这么多字，就写个 递归结束条件 都不会？

@nbndco 也就一行代码吧

@Cbdy 这个代码貌似是当年 doom 的作者写的

@rogerchen 这不正是应该考察应试者的问题嘛。。定义了一个接口， 让实现，说这个接口是错误的。好吧。
@debiann 那我错了。。开发者头条那喷了。 我并没有任何对回复者不屑的意思。

>
看来 V 站的程序猿素质高些, 哈哈. 我也认为 2 分(至少经过提示后), 应该能写出来才对. 不过实际面试过程中, 很难有人写出来. 题目就是 leetcode 上原题稍微变动加了个约束条件.

说归说, 能 show me your code 试试吗?


>
我想强调的不是说这道题目本身 而是说当有人给你一种思路后、能否在一步一步引导情况下思考并解决问题，最后能否将已经明白的思路变成实实在在的 code ，这肯定是较好的程序员应该具备的能力。

二分就是期待的答案，然而事实上就是并没有多少人写出。 结束条件就是一个坑给刷过这道题的人埋的，没刷过的人期望是经过提示后能写出二分。

楼上的代码貌似有不少是满足不了题意的


>
能写出牛顿迭代或者仅仅这种方法当然有好的印象加分， **看中的是在交流过程中思考解决问题的能力， 不是说这道题目写出来就 NB ， 写不出来就滚蛋**。


还有其他一些喷子， 麻烦好好看看原文好么。。。

http://mp.weixin.qq.com/s/0PsaOCR2k566SD9bRtgmlg

你们使劲喷吧， 让喷子来得更猛一些 喷之前， 求看完原文， 及想强调的东西。

我也当做自己在吃瓜 :)

不过， 可能题目文字上面描述得还可以更好。。。 对于某些人来说是比较排斥看什么公式的。


-----
哪条有不屑的意思？ 如果有， 可能回复给你的语气不太好吧？
再看看你的， “总的来说，你不是来问问题的，你想表达的就是：“我说的就是对的，其他都是垃圾。””
其实， 你前面部分， 我**挺认同**的。

“二分法是你期待的答案。
但二分法并不是一个好的答案。牛顿迭代法的收敛速度比二分法快很多。
这道题的重点不是怎么算出平方根（方法有很多），而是做误差分析。如果需要严格地证明误差小于一定的值，首先必须要有已知的参考值。所以要有数据类型允许的范围内一系列已知的答案才能完整地解这道题。
ls 给出了各种方法，都被你否认；虽然也没有考虑误差的问题，但你也没仔细想过。”

一直强调， 面试过程不是说要追求这道题目完成的答案。

咱俩的讨论， 就此打住吧。 如果有冒犯你的地方还请见谅。

简单、暴力解
```
function sq(v,t){
var i = 1;
var d = 1;
while(true){
if(i*i == v){
return i;
}
if(i*i < v){
i+=d;
} else {
i = i-d;
if(d < t){
break;
} else {
d*=0.1;
}
}
}
return i;
}
```

|r^2-v| <= t 是推不出来|r - \sqrt(v)| <= t 的吧，而且用|r*r - v|判断可能会溢出，应该用 r-2t <= (v-t^2)/r <= r+2t 来判断，这里假设 t^2<v ，如果大于 v ，直接返回 0 就行了。

膜一下 @msg7086 , 顺便楼主要的一行代码
sqrt = ->(v, t) { (0.0..v).bsearch { |x| (x-t) ** 2 < v && v < (x+t) ** 2 ? 0 : v - x ** 2 } }
sqrt.call(2, 0.001) # => 1.4140625

0x5f3759df

>>> def newton(x, y=1.0, tolerance=0.001):
... if (abs(y*y-x) < tolerance):
... return y
... else:
... return newton(x, (y+x/y)/2)
...
>>> newton(2)
1.4142156862745097
>>> newton(3)
1.7321428571428572
>>> newton(9)
3.00009155413138

我就来看有没有提 Carmack 的开根号，果然有

```
double sqrt(int v, double t){
double x = 1;
while(x*x -v > t || v - x*x > t){
x = x+(v-x*x)/(2*x);
}
return x;
}
```

想到平方根倒数速算法

最先想到的是方根倒数算法，其次是牛顿迭代法

奇怪……是我想的太简单了吗……感觉二分的条件很好写啊= =||
```
double simple_sqrt(double x, double e) {
double left = 0.0, right = 1.0 < x ? x : 1.0;
e = e < 0 ? -e : e;
if (x < e) return 0;

while (right - left >= e / 2) {
double middle = left + (right - left) / 2;
if (middle > x / middle) right = middle;
else left = middle;
}

return left;
}
```

```python
def sqrt(v, t):
"""assuming v is positive int, t is positive double"""
start = 1
end = v // 2
while True:
mid = start + (end - start) / 2.0
print('start = {}, mid = {}, end = {}'.format(start, mid, end))
if abs(mid * mid - v) <= t:
# we have abs(mid - sqrt(v)) <= abs(mid * mid - v) <= t
return mid
elif mid * mid < v:
start = mid
else:
end = mid
return start
```

想太多了，二分法下，限制 x 是正整数， v 是正小数的情况下，结束条件用 |x*x - v| <= t 就行。因为我们有：

t >= |x*x - v| = |x - sqrt(v)| * |x + sqrt(v)| >= |x - sqrt(v)|

泰勒级数 根下 x+1 在零点展开

``` java
public double sqrt(int v, double t) {
double min = 0;
double max = v;
double minRes = 0;
double maxRes = max * max;

double tmpMin = min;

while (v - minRes > t || maxRes - v > t) {
minRes = min * min;
if (minRes < v) {
tmpMin = min;
min = (min + max) / 2;
} else if (minRes == v) {
return min;
} else {
max = min;
maxRes = minRes;

min = tmpMin;
minRes = min * min;
}
}

System.out.println(min);
System.out.println(max);

return min;
}
```
结果:
3.005859375
3.0234375

@Med
``` java
public double sqrt(int v, double t) {
double min = 0;
double max = v;
double minRes = 0;
double maxRes = max * max;

double tmpMin = min;

while (v - minRes > t || maxRes - v > t) {
if (minRes < v) {
tmpMin = min;
min = (min + max) / 2;
} else if (minRes == v) {
return min;
} else {
max = min;
maxRes = minRes;

min = tmpMin;
}

minRes = min * min;
}

System.out.println(min);
System.out.println(max);

return min;
}
```
输出
2.98828125
3.0234375

牛顿法知道原理，但是公式不记得了，用二分法妥妥解决。
t 就是迭代结束的条件。

《计算机程序的构造和解释》开篇就讲这个。要不怎么说这是程序员的“圣经”呢。

@hanxiV2EX 看了一上午，长知识

public class Sqrt {

public static double sqrtBisection(double num, double deviation) {
return bisection(0, num, num, deviation);
}
public static double bisection(double left,double right,double num,double deviation) {
double center = (left + right)/2;
if (Math.pow(center-deviation, 2)<=num&&Math.pow(center+deviation, 2)>=num) {
return center;
}else if (Math.pow(center-deviation, 2)>num) {
return bisection(left, center, num, deviation);
}else {
return bisection(center, right, num, deviation);
}
}


public static void main(String[] args) {
System.out.println(sqrtBisection(10, 0.01));
}
}
结果为： 3.1640625
试着做了下

#include <stdio.h>
double eps = 0.1;
double abs(double x){
if(x < 0) return -x;
return x;
}
double sqrt(int v, double t){
double l = 0.0 , r = v + 0.0;
eps = t;
while(abs(r - l) <= eps){
double m = (l + r) / 2;
if(m * m > v) r = m;
else l = m;
}
return (l + r) / 2;
}
int main(){
return 0;
}

一般的算法竞赛者二分都是这样背的

sqrt' :: Double -> Double -> Double -> Double -> Double
sqrt' target buttom top t
| abs (result * result - target) < t * t = result
| result * result - target > 0 = sqrt' target buttom result t
| otherwise = sqrt' target result top t
where result = (buttom + top) / 2

sqrt :: Int -> Double -> Double
sqrt v t = sqrt' (fromIntegral v) 0 (fromIntegral v + 0.25) t

最近刚学 haskell 于是尝试着写了下，写的很难看 献丑了 orz