tailieunhanh - Less-Numerical Algorithms part 7

Moulton method 749 Adams’ stopping criterion 373 Adaptive integration 129, 141, 709, 714ff., 725ff., 733f., 737, 744, 749f., 797 Adaptive Monte Carlo integration 316ff., 319ff. | atArbitrary Precision 915 CITED REFERENCES AND FURTHER READING Bell . Cleary . and Witten . 1990 TextCompression Englewood Cliffs NJ PrenticeHall . Nelson M. 1991 The Data Compression Book Redwood City CA M T Books . Witten . Neal . and Cleary . 1987 Communications oftheACM vol. 30 pp. 520540. 1 atArbitrary Precision Let s compute the number n to a couple of thousand decimal places. In doing so we ll learn some things about multiple precision arithmetic on computers and meet quite an unusual application of the fast Fourier transform FFT . We ll also develop a set of routines that you can use for other calculations at any desired level of arithmetic precision. To start with we need an analytic algorithm for n. Useful algorithms are quadratically convergent . they double the number of significant digits at each iteration. Quadratically convergent algorithms for n are based on the AGM arithmetic geometric mean method which also finds application to the calculation of elliptic integrals cf. and in advanced implementations of the ADI method for elliptic partial differential equations . Borwein and Borwein 1 treat this subject which is beyond our scope here. One of their algorithms for n starts with the initializations Xo p2 no 2 p2 Yo p and then for i 0 1 . repeats the iteration Xi i i 1 Yi i Sample page from NUMERICAL RECIPES IN C THE ART OF SCIENTIFIC COMPUTING ISBN 0-521-43108-5 _ Xi i 1A x. Yi 1 Yi pXi i j y Xi i Yi 1 The value n emerges as the limit n1. Now to the question of how to do arithmetic to arbitrary precision In a high-level language like C a natural choice is to work in radix base 256 so that character arrays can be directly interpreted as strings of digits. At the very end of our calculation we will want to convert our answer to radix 10 but that is essentially a frill for the benefit of human ears accustomed to the familiar chant three point 916 Chapter 20. .