Đang chuẩn bị liên kết để tải về tài liệu:
Algorithms for programmers phần 10

Đối với các tính toán độ chính xác cao, người ta sẽ có chiều dài của các con số tính chữ số thập phân hoặc bit. Đối với các tính toán với ma trận vuông, người ta có thể đưa cho N số hàng. | CHAPTER 11. ARITHMETICAL ALGORITHMS 191 Combining two steps of the AGM iteration leads to the 4th order AGM iteration O0 p0 k 1 pk 1 k pa b0 k pk . 2 . Ok Pk o2k Pfe A 2 k pk cfc 2 Note that Ok pa2k and pk Vb2k. and R k 1 X - n 0 n pn VA 2 J J 11.197 11.198 11.199 11.200 11.201 11.202 corresponding to AGM4 1 pk cf. 5 p.17 . An alternative formulation of the 4th order AGM iteration is Ok pk k i --------2 11.203 Ok pk Ok 1 ---------2---- 11.204 Pk 1 H 1 k4 i 1 4 11.205 c2k 2 2 c2k 2 1 O4k_ 1 2 2 2 11.206 tv 2 tv 2 1 tv 1 tv tv 11.9.2 log The natural logarithm can be computed using the following relation cf. 5 p.221 log x R0 10 - n R0 10 -n x 10g 11.207 log x R0 10-n R0 10-n x 11.208 that holds for n 3 and x e 1 1 . Note that the first term on the rhs. is constant and might be stored for subsequent log-computations. See also section 11.10. hfloat src tz log.cc If one has some efficient algorithm for exp one can compute log from exp using y 1 de-x 11.209 log d x log 1 y 11.210 x log 1 1 de- x x log e - xd x x log d 11.211 Then log d x log 1 y x r y x- y y 2 3 11.212 Truncation of the series after the n-th power of y gives an iteration of order n 1 n xk x y y y 4-------- yy 2 3 n 1 11.213 xk 1 CHAPTER 11. ARITHMETICAL ALGORITHMS 192 Pade series P i j z of log 1 z at z 0 produce order i j 2 iterations. For i j we get i j 0 0 1 1 2 2 4 4 x P i j z 1 de x x z 6 z x z ---- 6 4z 30 21z z2 x z -------------- 30 36z 9z2 3780 6510z 3360z2 505z3 6z4 x z 3780 8400z 6300z2 1800z3 150z4 11.214 11.215 11.216 11.217 11.218 Compared to the power series based iteration one needs one additional long division but saves half of the exponentiations. This can be a substancial saving for high order iterations. 11.9.3 exp The exponential function can be computed using the iteration that is obtained as follows exp d x exp d log x x exp y where y d log x fl É _ _ y3 A x Ự y 2 3 The corresponding n-th oder iteration is _ ỵ A y2 y3 yn 1 xk 1 - xk xk 11 y 2 31 n 1 11.219 11.220 11.221 11.222 As .