徒手开根号和机器学习

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

前天的文章可点击阅读 《

算法的乐趣,你也可以懂

》。

首先我们来对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岁拟合剩下的差距,差距就只有一岁了。如果我们的迭代轮数还没有完,可以继续迭代下面,每一轮迭代,拟合的岁数误差都会减小。

怎么样,是不是有点像?

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

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181123G22VFM00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券