这个算法是平方收敛的（每次迭代有效位数增加一倍），

这样要求到Q位有效数字，就至少要log2Q+1次迭代



显然，这种计算是要高精度表示的，

我所用的算法就是普通的高精度加减乘除

加减是O(n)的，时间花费很少。

乘除是O(n2)的，主要的时间花费都在这上面。



而由这个算法中可以看到，bn的计算需要开根号。

这里有两种开根号的办法：

①用初中教我们的方法，每次开两位根号，用除法减掉，

这样所需时间为n2·n/2=O(n3),不可忍受！

②用牛顿迭代法。

即

x0=任意正数，

xn+1=(xn+a/xn)/2

同样，这个算法也是平方收敛的。

其中除法是O(n2)的

故还是需要O(n2log2n)的时间

-Square convergence of the algorithm is (each iteration doubles the effective number of bits),

Such a request to the Q digits to at least log2Q 1 iterations



Obviously, this calculation is expressed to high accuracy,

The algorithm I used is the ordinary high-precision addition, subtraction

Addition and subtraction is O (n), the time spent very little.

Multiplication and division is O (n2), mainly time spent in this way.



By this algorithm can be seen, bn square root calculation needs.

There are two ways to open root:

① The middle school to teach our method, each time to open the two radicals, with the division to lose,

This time is n2 · n/2 = O (n3), can not stand it!

② The Newton iteration.

That

x0 = any positive number,

xn 1 = (xn a/xn)/2

Similarly, the square is also the convergence of the algorithm.

One division is O (n2) of the

It still needs O (n2log2n) time