The Art of Computer Programming: Seminumerical algorithms, Volume 2Br> The Art of Computer Programming 2. Seminumerical Algorithms by Knuth, Donald E. Terms of use Finally, after a wait of more than thirty-five years, the first part of Volume 4 is at last ready for publication. Check out the boxed set that brings together Volumes 1 - 4A in one elegant case, and offers the purchaser a $50 discount off the price of buying the four volumes individually. The Art of Computer Programming, Volumes 1-4A Boxed Set, 3/e ISBN: 0321751043 Descriptive content provided by Syndetics"! a Bowker service. Table of Contents The Art of Computer Programming 2. Seminumerical Algorithms by Knuth, Donald E. Terms of Use 3 Random Numbers Introduction Generating Uniform Random Numbers The Linear Congruential Method Other Methods Statistical Tests General Test Procedures for Studying Random Data Empirical Tests Theoretical Tests The Spectral Test Other Types of Random Quantities Numerical Distributions Random Sampling and Shuffling What Is a Random Sequence? Summary 4 Arithmetic Positional Number Systems Floating Point Arithmetic Single-Precision Calculations Accuracy of Floating Point Arithmetic Double-Precision Calculations Distribution of Floating Point Numbers Multiple Precision Arithmetic The Classical Algorithms Modular Arithmetic How Fast Can We Multiply? Radix Conversion Rational Arithmetic Fractions The Greatest Common Divisor Analysis of Euclid's Algorithm Factoring into Primes Polynomial Arithmetic Division of Polynomials Factorization of Polynomials Evaluation of Powers Evaluation of Polynomials Manipulation of Power Series Answers to Exercises Appendix A Tables of Numerical Quantities Fundamental Constants (decimal) Fundamental Constants (octal) Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers Appendix B Index to Notations Index and Glossary. 0201896842T03062003 Descriptive content provided by Syndetics"! a Bowker service. Excerpt The Art of Computer Programming 2. Seminumerical Algorithms by Knuth, Donald E. Terms of Use O dear Ophelia! I am ill at these numbers: I have not art to reckon my groans. --Shakespeare, "Hamlet", Act II, Scene 2, Line 120 The algorithms discussed in this book deal directly with numbers; yet I believe they are properly called seminumerical, because they lie on theborderline between numeric and symbolic calculation. Each algorithm not onlycomputes the desired answers to a numerical problem, it also is intended toblend well with the internal operations of a digital computer. In many casespeople are not able to appreciate the full beauty of such an algorithm unlessthey also have some knowledge of a computer's machine language; the efficiencyof the corresponding machine program is a vital factor that cannot be divorcedfrom the algorithm itself. The problem is to find the best ways to make computers deal with numbers, and this involves tactical as well as numerical considerations. Therefore the subject matter of this book is unmistakably a part of computer science, as well as of numerical mathematics. Some people working in "higher levels" of numerical analysis will regard thetopics treated here as the domain of system programmers. Other people working in"higher levels" of system programming will regard the topics treated here asthe domain of numerical analysts. But I hope that there are a few people left who will want to look carefully at these basic methods. Although the methods reside perhaps on a low level, they underlie all of the more grandiose applications of computers to numerical problems, so it is important to know them well. We are concerned here with the interface between numerical mathematics and computer programming, and it is the mating of both types of skills that makes the subject so interesting. There is a noticeably higher percentage of mathematical material in this book than in other volumes of this series, because of the nature of the subjects treated. In most cases the necessary mathematical topics are developed here starting almost from scratch (or from results proved in Volume 1), but in several easily recognizable sections a knowledge of calculus has been assumed. This volume comprises Chapters 3 and 4 of the complete series. Chapter 3 isconcerned with "random numbers": It is not only a study of various ways togenerate random sequences, it also investigates statistical tests forrandomness, as well as the transformation of uniform random numbers into othertypes of random quantities; the latter subject illustrates how random numbersare used in practice. I have also included a section about the nature ofrandomness itself. Chapter 4 is my attempt to tell the fascinating story ofwhat people have discovered about the processes of arithmetic, after centuriesof progress. It discusses various systems for representing numbers, and how toconvert between them; and it treats arithmetic on floating point numbers, high-precision integers, rational fractions, polynomials, and power series, including the questions of factoring and finding greatest common divisors. Each of Chapters 3 and 4 can be used as the basis of a one-semester collegecourse at the junior to graduate level. Although courses on "Random Numbers"and on "Arithmetic" are not presently a part of many college curricula, Ibelieve the reader will find that the subject matter of these chapters lendsitself nicely to a unified treatment of material that has real educationalvalue. My own experience has been that these courses are a good means ofintroducing elementary probability theory and number theory to collegestudents. Nearly all of the topics usually treated in such introductorycourses arise naturally in connection with applications, and the presence ofthese applications can be an important motivation that helps the student tolearn and to appreciate the theory. Furthermore, each chapter gives a fewhints of more advanced topics that will whet the appetite of many students forfurther mathematical study. For the most part this book is self-contained, except for occasional discussions relating to theMIXcomputer explained in Volume 1. Appendix B contains a summary of the mathematical notations used, some of which are a little different from those found in traditional mathematics books. Preface to the Third Edition When the second edition of this book was completed in 1980, it represented thefirst major test case for prototype systems of electronic publishing calledTeXandMETAFONT. I'am now pleased to celebrate the full development of those systems by returning to the book that inspired and shaped them. At last I am able to have all volumes of The Art of Computer Programming in a consistent format that will make them readily adaptable to future changes in printing and display technology. The new setup has allowed me to make many thousands of improvements that I have been wanting to incorporate for a long time. In this new edition I have gone over every word of the text, trying to retainthe youthful exuberance of my original sentences while perhaps adding some moremature judgment. Dozens of new exercises have been added; dozens of old exercises have been given new and improved answers. Changes appear everywhere, but most significantly in Sections 3.5 (about theoretical guarantees of randomness), 3.6(about portable random-number generators), 4.5.2(about the binary gcd algorithm), and 4.7(about composition and iteration of powerseries). The Art of Computer Programming is, however, still a work in progress. Research on seminumerical algorithms continues to grow at a phenomenal rate. |
Contents
Chapter 3 Random Numbers | 1 |
Chapter 4 Arithmetic | 194 |
Answers to Exercises | 538 |
Copyright | |
2 other sections not shown
Other editions - View all
The Art of Computer Programming: Seminumerical Algorithms, Volume 2 Donald E. Knuth Limited preview - 2014 |
Common terms and phrases
a₁ addition chain approximately assume b₁ bits calculation coefficients Comp compute consider continued fraction decimal defined definition digits discussed distribution divide division elements equal equation Euclid's algorithm evaluate example exercise exponent floating point floating point numbers formula function given greatest common divisor hence Horner's rule input irreducible irreducible polynomials iterations Lemma linear congruential linear congruential sequence m₁ Math matrix modulo multiplication multisets nonnegative nonzero normal notation number system obtain operations output period length positive integer possible prime factors primitive polynomial probability problem proof prove quotient radix radix point random number real numbers relatively prime representation result satisfies Section solution spectral test step subroutine subtraction Theorem tijk two's complement U₁ unique factorization domain V₁ variables vectors Xn+1 y₁ zero