Summary Chapter Four. Arithmetic 4. Positional Number Systems 4. Single-Precision Calculations 4. Accuracy of Floating Point Arithmetic 4. Double-Precision Calculations 4. The Classical Algorithms 4. Radix Conversion 4. The Greatest Common Divisor 4. Factoring into Primes 4. Evaluation of Powers 4. Evaluation of Polynomials Chapter Five. Sorting 5. Internal Sorting 5. Sorting by Insertion 5. Sorting by Exchanging 5. Sorting by Selection 5. Sorting by Merging 5. Sorting by Distribution 5. Minimum-Comparison Sorting 5.
Summary, History, and Bibliography Chapter Six. Searching 6. Sequential Searching 6. Searching an Ordered Table 6. Binary Tree Searching 6. Balanced Trees 6. Digital Searching 6. Hashing Answers to Exercises 1.
Input and Output 2. The book contains a selection of carefully checked computer methods, with a quantitative analysis of their efficiency. Outstanding features of the second edition include a revised section on optimum sorting and new discussions of the theory of permutations and of universal hashing. Here he presents the third volume of his guide to computer programming.
The first three volumes of this work have long comprised a unique and invaluable resource in programming theory and practice. In this long-awaited new volume, the old master turns his attention to some of his favorite topics in broadword computation and combinatorial generation exhaustively listing fundamental combinatorial objects, such as permutations, partitions, and trees , as well as his more recent interests, such as binary decision diagrams.
I distinctly remember the small used bookstore where I purchased Volume 1. I was devoted to Math at the time. Math was hard, deep, and precise, which I loved.
I regarded programming as interesting, but somewhat tedious and not too challenging. Volume 1 changed that perception for me. I discovered that programming could be not only challenging but elegant as well. It was a real science. It made me think. Knuth's books gave me even more. The amazing rigor presented in every page pushed me to do the same in my career. I think this was the best lesson they provided. I miss that rigor today. I hope someone out there is considering extending this series to tackle the new breed of computer science problems with the same rigor.
Many of today's problems, such as communication, search, and user interface problems, are more people oriented and therefore harder to define, but the rigor is still needed.
Having the books on my bookshelf gave me a sense of security Today Wikipedia serves some of that purpose. It would have been nice 20 years ago to have had a more portable version of Knuth so that I could know, wherever I was, that I could quickly look something up. But 20 years ago there was nothing else, so I'd have to wait until I was back at home to consult the copy in my bedroom bookshelves, or wander the halls at work to find someone who had a copy in their office.
I did actually have a 2nd copy that was supposed to be at work, but it was always being "borrowed", so I could never find my own copy at work when I needed it.
The Scientific Center, located at N. Market Street, had a wonderful mathematics library, and when I expressed some interest in computing some fundamental constants to many decimal places, the staff probably Don Orth directed me to Seminumerical Algorithms , Volume 2 of Knuth's magnum opus, The Art of Computer Programming.
Reading it was like stepping into a new world. Knuth revealed that doing a good job at programming was more than just putting together lines of code and timing them. One could actually analyze algorithms, determining their running times with great precision. One could prove mathematically that one algorithm was superior to another, and quantify how much better.
And the analysis led to all sorts of amazing mathematics, involving asymptotic expansions, power series, and continued fractions. It fundamentally changed the way I viewed the computer. Almost every page of Seminumerical Algorithms revealed something interesting. On one page, I learned about the binary gcd algorithm, an improvement on Euclid's algorithm. On another, a method for determining the continued fraction for any algebraic number that did not involve computing the number in decimal first.
On another, a faster way to factor integers. Lacking the funds to buy the book, I began to photocopy pages that interested me.
After a month or so I had photocopied almost the entire book. And look! Knuth even offered a reward for readers who found errors in his book!
In , as a high school senior, I found an error a small mistake in a factorization table , and sent it off to Knuth.
0コメント