Continue fraction

05 Jan 2021 -

论cf，没错，这个cf并不是游戏，也不是codeforces，而是continue fraction，其实这个连分数没什么用（划），其实这个连分数能解2次方程，这要从一次作业讲起。

记得有一次老师布置了一个作业，有一道题是这样的：“有一个等边三角形，3条边都是6cm，高是5.2cm，求……”。

然后我发现，3条边都是6cm，说明p=9cm（海伦公式），因此三角形面积是93^3的平方根，也就是9根号3，然后可算出高为根号27，而5.2的平方=26/5的平方=26的平方/25=25^2+50+1/25=23100+25+50+1/25=676/25=27+(1/25).所以我找到了数学老师说老师这里不应该说高是5.2cm，应该说约是！然后老师说这个没啥嘛，为了方便你们懂。可是我还是很疑惑，不过这次我讲的不是海伦公式，不是三角形，是如何开方。

丢番图逼近

没错这才是主题

一个数如何开方，第一个想到的可能是暴力，其实还有一种我叫做牛顿法的玩意，例如对654开方，先看654/2=327,它的平方比654大太多，因此选择327和1的平均数124进行平方，很明显还是太大，那么选择62进行平方，很明显还是太大，然后选择31进行平方，很明显还是太大，然后选择16进行平方，很明显太小，然后选择31和16的平均数（取整）24,24的平方稍微小了点，取27，大了点，取25到26，然后发现654的平方根大约是25.5，不需要太多的计算，那么，怎么才能快速知道小数后的精确值呢？

我们请出连分数：,这时候，

此时我们可以愉快地求654的连分数啦。