求根号2的小数点后10000位,字节面试题随想

淩亂°似流年 2022-08-30 01:43 34阅读 0赞

### 起因 ###

昨天在群里有一个小伙伴发了一道字节后端的面试题, 题干是要求 2 \\sqrt\{2\} 2的小数点后10000位, 经过自己的一些直观思考和网上查阅资料后, 大致有如下3种方案, 由于很多语言里的小数精度都达不到10(-10000)级别, 所以这题目我们简化到小数点后6位吧

### 方法一, 直观的二分法 ###

假设给的数字为*n*, 可以设置左边界为0, 右边界为n, 取mid = (0 + n) / 2, 如果mid2 小于n, 令左边界为mid, 否则有边界为mid, 终结循环的条件是左右边界的差小于精度的阈值(right - left < threshold), 简单的代码如下:

double getSqrt(int n, double threshold)
    	double left = 0, right = n;
    	while ( right - left > threshold){ 
    		double mid = (left + right) / 2;
    		if (mid * mid == n) return mid;
    		else if (mid * mid < n) left = mid;
    		else right = mid; 
    	} 
    	return left;

逻辑比较简单, 就不作过多注释了

### 方法二, 牛顿迭代法 ###

牛顿迭代法理论上是可以求出绝大多数多项式的根(最低要求是该函数二阶可导, 这一点不是本文讨论的范畴, 于是略过), 大体的思想如下:  
已知曲线方程*f(x)*, 要求方程的根, 在 x n x\_n xn处作切线, 求 x n + 1 x\_\{n+1\} xn\+1, 这里的 x n x\_n xn是迭代过程中某一个解, 最初的解可以任意设置, 不过尽量准确会比较好.  
通过求导易得 x n x\_n xn的切线方程为 f f f( x n x\_n xn) +  f ′ f' f′( x n x\_n xn)( x x x\- x n x\_n xn),  
化简可以求出  x n + 1 = x n − f ( x n ) f ′ ( x n ) \{x\_\{n+1\} = x\_n - \\frac \{f(x\_n)\} \{f'(x\_n)\}\} xn\+1=xn−f′(xn)f(xn)  
那么就可以不断地迭代这一过程, 终止条件就是 x n − x n + 1 < t h r e s h o l d \{x\_n\} - \{x\_\{n+1\}\} < threshold xn−xn\+1<threshold  
对于本题来说,  f ( x ) = x 2 − n f(x) = x^2 - n f(x)=x2−n, 对应的 f ′ ( x ) = 2 x f'(x) = 2x f′(x)=2x, 因此代码如下

double getSqrtNt(double n, double threshold){
    	doulbe x_n1 = n / 2;  //起始点设置, 这是我随便写的一个, 可以有更好的方法
    	double x_n = n;
    	while (abs(x_n1 - x_n) > threshold){
    		x_n = x_n1;
    		x_n1 = xn - (xn * xn - n)/(2 * xn)
    	}
    	return xn;
    }

### 方法三, 连分数法, 适用于手算 ###

其实这个方法本质上跟牛顿迭代法一样, 对于导数不太熟练的同学可以适用这种方法, 并且这个方法的条件比较苛刻, 有两点

1.  仅适用开平方
2.  被开方数为正整数  
    步骤如下, 要求 s \\sqrt\{s\} s, 先将其分解为  s = a 2 + b s = a^2 + b s=a2\+b, 其中 a 2 > > b a^2 >> b a2>>b, 然后根据要求的精度  
     s = a + b 2 a + b 2 a + . . . \\sqrt\{s\} = a + \\frac \{b\} \{2a + \\frac \{b\} \{2a + ...\}\} s=a\+2a\+2a\+...bb  
    举个例子, 求150的开方, 首先找到 150 = 12 ∗ 12 + 6 150 = 12 \* 12 + 6 150=12∗12\+6

*  求一阶的情况,  150 = 12 \\sqrt\{150\} = 12 150=12
 *  第二阶,  150 = 12 + 6 / 24 = 12.25 \\sqrt\{150\} = 12 + 6/24 = 12.25 150=12\+6/24=12.25, 此时精度更高了一些
 *  第三阶,  150 = 12 + 6 / ( 24 + ( 6 / 24 ) ) = 12.2474 \\sqrt\{150\} = 12 + 6/(24 + (6/24)) = 12.2474 150=12\+6/(24\+(6/24))=12.2474, 更高了一些
 *  … 越深精度越高  
    查询计算器的 150 \\sqrt\{150\} 150的值为12.24744, 已经很接近我们的答案了  
    证明的方法也很简单, 在后面笔者会贴上李永乐老师相关的证明

## References ##

\[1\][如何通俗易懂地讲解牛顿迭代法求开方？数值分析？ - 马同学的回答 - 知乎][- _ -]  
\[2\][如何手算开平方？学会这个你又能跟小伙伴炫耀了！][Link 1]

[- _ -]: https://www.zhihu.com/question/20690553/answer/146104283
[Link 1]: https://www.youtube.com/watch?v=NXexkJyPoQs&t=193s