並行處理計算根號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)