首先让我们回顾下上节课讲的，用牛顿法计算√2的内容：

简单来说，牛顿法从x0=1不断向后计算逼近√2的值，而刚开始计算的精度是1，随着牛顿法的逼近（共log2d个循环），就能使得√2逼近值的精度达到d。在逼近过程中，精度的变化为Quadratic convergence二次收敛趋势（即1,2,4,6,….），为了证明这个，讲师给出了下图内容：

假设xn = √a (1+εn) 且εn随着n增加，不断趋于0，本质上来说就是xn = √a，加了(1+εn)是为了方便我们证明二次收敛的存在。之后根据牛顿法xi+1 = (xi + a/xi) /2对其进行xn+1的计算个，我们便能得到εn+1= εn2 / 2(1+εn)，而由于εn随着n增加，不断趋于0，所以(1+εn)本质为1，那么最后很容易就看出εn+1是跟εn成二次关系。

一、高精度乘法

另外上节课我们还讲了如何进行高精度乘法，这节课，讲师将它们总结并加以补充如下图所示：

以上五种方法，从上到下，时间复杂度逐渐减少，值得提到的就是，Toom-Cook方法本质跟Karatsuba方法一样的，只不过前者在数的拆分上多了一个而已，即前者为x0,x1,x2，而后者为x0,x1。

二、高精度除法

问：如果我们想要计算一个关于a/b的高精度结果，该怎么做？

答：我们先计算R/b，然后对它结果向下取整，然后再用之前高精度乘法来乘a就好了。记住这里的R是一个非常大的值，特别的是R很容易除别人，例如R=2k这样的。

问：那请问R/b怎么计算？

答：用牛顿法，具体过程如下图所示：

三、时间复杂度

问：高精度除法的时间复杂度是多少？

答，是Ο(log2n * nα)，也可近似于Ο(nα)，具体计算如下：

问：高精度乘法的时间复杂度是多少？

答，之前在第一部分就有不同方法下的时间复杂度，但总结来说就是Ο(nα) α≥1。

问：高精度计算平方跟的时间复杂度是多少？

答：如下图所示，本质就是不断使用牛顿法配合高精度乘除法使用，结果近似为Ο(nα)。

有上面三个问题我们能得到：在时间复杂度上，高精度乘法 ≡ 高精度除法 ≡ 高精度求平方根 ≡ Ο(nα)。注意‘≡’为本质相同的意思，不代表完全相同，还是有略微差别的。