徒手开根号和机器学习

前天的公号文章里提到了“徒手开根号”，如果你不了解，可能有不明觉厉之感，今天我来给大家解读一下这个徒手开根号，其实很简单，而且你们已经至少会了一半了。

前天的文章可点击阅读 《

算法的乐趣，你也可以懂

》。

首先我们来对4开方，这个简单，大家都会，二二得四，4的开方是2。别看简单，其实也有学问，请大家想一想你是用什么方法求得呢？ 我觉得这一问会把很多人都问愣了，2乘2分明得4，4的开方就是2，还要什么方法啊。 其实，你用的就是“凑”和“试”的这种方法，因为简单，所以一试就得到答案。

如果我让你对625开方呢？这回一下“试”不出来了，你可能会多试几次，然后发现25乘25正好是625，所以求出625的开方是25。

下面我们来看5。二二得四，三三得九，5在中间，开方不可能是整数了，这个大家一看就知道，于是不知道怎么求了。其实道理和上面一样，继续“试”就可以了。我们先来看最简单粗暴的方法，在算法里通常把这类方法叫蛮力法，意思是没多少技术含量，但是也能解决问题。

我们知道5的开方肯定在2和3之间，那就从2.1到2.9开始逐个尝试，求平方再和5比，然后发现2.2的平方小于5，2.3的平方大于5，所以5的开方在2.2和2.3之间，以此类推，继续在2.21和2.29之间尝试，只要你愿意，你就能求的任意精度的值。简单吧？

不过肯定有人发现了，这么干也太麻烦了，一个个试要尝试很多个数，特别是想要求小数点后更多位时，每次都要计算一个很大数的平方，不具有可操作性。确实，这个“算法”的效率太低了，但思路其实已经有一半了，下面我们需要更多的一点技巧。

我们尝试一个大一点的数，以对 198.7 这个数进行开方为例子。

第一步，我们以小数点为界限，把要求的数两两分组，如下：

01 98. 70 00 00 （补0纯粹为了看起来整齐，后面只要需要可以随意补）

然后，你可以暂时去掉小数点（别担心，最后再补回来就行），得到如下形式

01 98 70 00 00

下面正式开始计算（你如果真想学一下而不是看热闹，最好准备纸笔，我们是徒手开平方，不是徒口开平方）：

0. 先考虑第一对数据：0198 70 00 00

1. 在0 到 9 之中找一个数，令它的平方最接近且不大于上面的蓝色数据，这个凑到的数，此处为1

2. 蓝色数和红色数的平方做差得到b： b =01- 1*1 = 0

3. 将b和下一对数据组成新的数据：0 9870 00 00

4. 对已经求得的红色数乘以20，得到 c = 20*1 = 20

5. 在0 到 9 之中找一个数d，使得 e = d*c + d*d 最接近且不大于上面的蓝色数据（098），这一步稍微难一点，但是考虑到只需要去试 0 - 9 之间的数字，大家还是能应付的。此处得到为 d = 4， 并且 e = 96。将d和上面的红色数字组成新的新的数14

6. 蓝色数据和e的差： b =098- 96 = 2

7. 将b和下一对数据组成新的数据：27000 00

8. 对已经求得的红色数乘以20，得到 c = 20*14= 280

9. 在0 到 9 之中找一个数d，使得 e = d*c + d*d 最接近且不大于上面的蓝色数据（270）。此处得到为 d = 0， 并且 e = 0。d和上面的红色数字组成新的新的140

（下面你重复6到9得过程就可以了）

6. 蓝色数据和e的差： b =270- 0 = 270

7. 将b和下一对数据组成新的数据：270 0000

8. 对已经求得的红色数乘以20，得到 c = 20*140= 2800

9. 在0 到 9 之中找一个数d，使得 e = d*c + d*d 最接近且不大于上面的蓝色数据（27000）。此处得到为 d = 9， 并且 e = 25281。d和上面的红色数字组成新的新的1409

6. 蓝色数据和e的差： b =27000- 25281 = 1719

7. 将b和下一对数据组成新的数据：1719 00

8. 对已经求得的红色数乘以20，得到 c = 20*1409= 28180

9. 在0 到 9 之中找一个数d，使得 e = d*c + d*d 最接近且不大于上面的蓝色数据（171900）。此处得到为 d = 6， 并且 e = 169080。d和上面的红色数字组成新的新的14096

... ... ...

（毕竟没有黑板，我只能做到上面那样了，真有兴趣得可以再去百度一下）如果想要算得更准，还可以继续补零，重复这个过程。红色数就是我们要得结果，这时候把小数点加在合适的位置，相信你不会弄错，最后得到14.096，用Python验证一下：

没错，算出来的位数都是正确的。

等等，好像也不简单……

嗯，是得，简单还有什么意思？ 你要算的不是加减乘除，可是开根号啊。所以口算是不行的，上面有些乘法位数比较多，需要用笔。但上过初中的都能hold住这写乘法。

如果你愿意，请思考一下这个算法和上面提到的第一种算法有什么区别。

算法一，每次也是要去试，但是每次都要去算整个数的平方，去和5比较。比如我算出来5的根号在 2.2 和2.3之间，我要从2.21开始去计算 2.21的平方，然后和5去比较。试想一下，如果我们已经算出的位数很多，已经算到2.236了，那么你下面需要计算 2.236的平方，这个可比后一种方法的计算量大多了吧？而且求得位数越多越明显，所以这个算法不具有可操作性，真正徒手起来，是不行的。

再看算法二，每次也要去凑一个数，但并不是去凑和 198.7 接近的数，而是一组组得开始，并且和前几步得到的一个“差”去相比，算法二成功利用了已经求出的结果，每一步都把问题简化一些，所以这个徒手开根号的可操作性才更好。

那么，回到标题，这个算法跟机器学习什么关系？

机器学习里有一个算法叫梯度提升树，简称GBDT，非常有名。GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。

怎么样，是不是有点像？

如果你有不明白得地方，或者想知道后一个算法是怎么来的，请在评论区或后台留言。

下面是两个不一样的二维码，不信扫扫看