并行处理计算根号2问题解答(修改版)

假设你有N台机器. 如何能最快地计算出根2 的小数部分. 假设每台机
器可以执行M条指令每秒 (64位机器), 请估计一下, 如果要计算出sqr2小数
点后面T位的时间.

解：

现在假设N>11，每台机器计算一次乘法的时间为 d，加减法时间 d/4,
机器的通讯时间忽略。机器编号从0排到N。

用N-1进制计算小数点后面T位

(N-1)^p = 10^T

P = T/lg(N-1)

也就是说，N-1进制计算小数点后P位等于10进制计算小数点后T位

机器N早已算出根的第一位，我们就把它叫作“商”，也算出“余数”。
算出 c = (N-1)*(N-1)
机器N把商送给其它机器。

其它机器 k 做如下操作：

x = (2*(N-1)*商 + k)*k,
耗时 2d + d/4
接受机器N传来的余数
商 = 商*(N-1) + k
耗时3d + d/2( 常数 2*(N-1)，(N-1) 早已存在 机器 k 中)
余数 = 余数-x，
耗时3d + 3d/4
如果余数大于等于0,向机器k-1发送一个“比你好”的信息

余数大于等于0且没有接到“比我好”的信息的机器把 商 和 余数
送给机器N。

其它机器 N 做如下操作：

机器N把某个机器k送来的商 和 余数作为新 商 和 余数。
把商传给机器 k
余数 = 余数*c
耗时d
把余数传给机器 k

下一位的计算是类似的。循环P次后，总时间是

3.75dT/lg(N-1)