计算机是如何开根号的？sqrt是如何实现的？

2023-12-17 20:18| 来源: 网络整理| 查看: 265

我们经常会用到sqrt()这个函数，c、c++里加个头文件，java里导入个包，然后啪啪啪随便一敲，一个数就被开根号了。

那么sqrt()到底是如何实现的？

今天我将简单介绍三种方法，告诉你sqrt()函数实现的秘密。

一、二分法

这里就不详细介绍了，就是个简单的二分板子。

但是当我们写完这段代码运行的时候就会发现，数一大，或者要求的精度一高，耗费的时间会非常长。

public static double sqrt(double c) { double l = 0, r = c / 2, mid = 0.0; while (l c) { r = mid; } else { break; } } return mid; }

二、牛顿迭代法

（这种方法的时间复杂度比java内自带的函数稍高一点。）

什么是牛顿迭代法呢？

牛顿迭代法（Newton's method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。（摘自百度百科）

那么牛顿迭代法在开根号上到底有什么用呢？

换个思路想一想，求一个数c的根号，可以转化成求 $x^{2}=c$ 的解，那么设 $y=x^{2}-c$ ，根据下图的牛顿迭代公式就能无限近似r；

牛顿迭代法

先把代码放上，对代码中迭代部分不懂的话，可以看下简单的证明：

$x_{i}=x_{i-1}-\frac{f(x_{i-1})}{f'(x_{i-1})}\Rightarrow x_{i}=x_{i-1}-\frac{x_{i-1}^{2}-c}{2*x_{i-1}}\Rightarrow x_{i}=(x_{i-1}+\frac{c}{x_{i-1}})/2$

public static double sqrt1(double c) { double x1 = c; double x2 = c / 2; while (Math.abs(x1 - x2) > 1e-7) { x1 = x2; x2 = (x1 + c / x1) / 2;// 迭代核心代码，证明见博文 } return x1; }

三、一个神奇的方法

对于代码的解释，可以看下下面几位大佬的解释：

https://www.cnblogs.com/shizhh/p/5775578.html

https://blog.csdn.net/qq_26499321/article/details/73724763

还有一篇相关论文：

http://www.matrix67.com/data/InvSqrt.pdf

public static float invSqrt(float x) { float xhalf = 0.5f * x; int i = Float.floatToIntBits(x); i = 0x5f37642f - (i >> 1); x = Float.intBitsToFloat(i); x = x * (1.5f - xhalf * x * x); return 1 / x; }

【本文地址】

公司简介

联系我们