The Art of Computer Programming, Volume 2: Seminumerical Algorithms

Art of Computer Programming

by Donald Ervin Knuth

The bible of all fundamental algorithms and the work that taught many of today's software developers most of what they know about computer programming. – Byte , September 1995 I can't begin to tell you how many pleasurable hours of study and recreation they have afforded me! I have pored over them in cars, restaurants, at work, at home... and even at a Little League game when my son wasn't in the line-up. –Charles Long If you think you're a really good programmer... read [Knuth's] Art of Computer Programming... You should definitely send me a resume if you can read the whole thing. –Bill Gates It's always a pleasure when a problem is hard enough that you have to get the Knuths off the shelf. I find that merely opening one has a very useful terrorizing effect on computers. –Jonathan Laventhol The second volume offers a complete introduction to the field of seminumerical algorithms, with separate chapters on random numbers and arithmetic. The book summarizes the major paradigms and basic theory of such algorithms, thereby providing a comprehensive interface between computer programming and numerical analysis. Particularly noteworthy in this third edition is Knuth's new treatment of random number generators, and his discussion of calculations with formal power series.
Ebook (PDF version) produced by Mathematical Sciences Publishers (MSP),

Genres: Computer Science, Programming, Nonfiction, Algorithms, Computers, Technology, Reference

784 pages, Hardcover

First published January 1, 1969

About the author

Donald Ervin Knuth, born January 10th 1938, is a renowned computer scientist and Professor Emeritus of the Art of Computer Programming at Stanford University.

Author of the seminal multi-volume work The Art of Computer Programming ("TAOCP"), Knuth has been called the "father" of the analysis of algorithms, contributing to the development of, and systematizing formal mathematical techniques for, the rigorous analysis of the computational complexity of algorithms, and in the process popularizing asymptotic notation.

In addition to fundamental contributions in several branches of theoretical computer science, Knuth is the creator of the TeX computer typesetting system, the related METAFONT font definition language and rendering system, and the Computer Modern family of typefaces.

A prolific writer and scholar, Knuth created the WEB/CWEB computer programming systems designed to encourage and facilitate literate programming, and designed the MMIX instruction set architecture.

Reviews

[Eugene Miya · Rating 5 out of 5]

A short story: some years ago, a Silicon Valley institution existed named Computer Literacy Bookshop founded by a couple of friends and run by a 3rd. They sold the shop to a couple of guys who owned the cbooks domain, and they decided to have a book signing with Knuth for the newly reprinted TeX versions of TAOCP. I was lucky to be invited to a dinner before hand. The new owners reached out to shake Don's hand when one asked the question: "Are there any applications for Fibonacci numbers?" Which caused me to roll my eyes in the back of my head, and thinking "Oh, a few dozen", which was basically Don's answer.

This is why one reads Vol. 2.

Until DEK wrote vol. 2 this was a little researched area in math. TAOCP is more a reference to important algorithms which aren't purely numerical methods (excepting sorting and searching, saved for Vol. 3).

If any single criticism for TAOCP stands out, it's that Don has chosen to stick with MIX (and MMIX) rather than higher level languages like Pascal (in his time) or C/C++, or Java, or what ever easier to program future language comes along. Don has his reasons to illustrate lower level machine function. Bear with him. Vol. 2 is an incredible reference, and you will be able to understand more the Fibonacci answer.

[marcel · Rating 5 out of 5]

This is the TAOCP book I see referenced/recommended the least, and admittedly it is the one I have found least useful as a reference so far. But, for me, it was the most enjoyable read of them all. The first two-hundred pages deal with methods for generating random numbers and checking if a sequence is sufficiently random. At times, Knuth gets quite philosophical, and the main takeaway of this chapter is that there isn't a totally well-defined concept of what a random sequence should be, at least as far as computers are concerned. The second chapter of this volume deals with arithmetic, starting with methods for representing floating-point numbers in memory and then diving into algorithms for adding, multiplying, factoring, etc. A detailed analysis of every single algorithm is given, and Knuth doesn't just restrict himself to real numbers; this chapter discusses generalises many of these operations to modular arithmetic, polynomials, matrices, and power series as well. All in all, this volume concerns the concepts that modern programmers take for granted on a day-to-day basis: the ability for a computer to perform basic arithmetic operations quickly.

[Abdellah · Rating 5 out of 5]

The book it is the secound volume in this series of book . it covers a wide range of topics, including

- sorting and searching in this topic it covers various sorting and searching algorithms techniques like quicksort , marge sort, radix sort ...

- Combinatorial Algorithms : it covers various combinatorial algorithms and techniques including generating permutations and combinations, generating and manipulating pertations and set partitions.

- Recursive Algorithms : it covers various recursive algorithms and techniques, such as recursion and mathematical induction. and the analysis of recursive algorithms.

- Random Numbers : it covers the generation of random numbers and the use of random numbers in algorithms

- Backtracking and Dynamic Programming : it covers backracking and dynamic programming, which are important techniques for solving many type of problems such as 10queen problem.

Overral. this section of the book is considered to be a classic and an essential reference for computer scientists and programmers, known for its comprehensive coverage, clear explanations, and rigor ....

[Josh Berry · Rating 5 out of 5]

This was a much denser volume than the first volume. To say that it went over my head in many parts would be an understatement. It is interesting to see the points for where highly computationally intensive applications will have to be concerned.

The first half is a good warning to consider before you try and do anything "random." It actually begins with simple tests that are very intuitive to determine how random a series is and builds up to some fairly comprehensive tests.

Interestingly, the intro to the second half is just plain fun for a brief history of arithmetic. To the point that you will feel like such a "simple" discipline will seem almost alien. Very impressive.

At any rate, I do plan on revisiting sections later. Not sure I will make a ton more progress, but you won't know till you try. And many of these topics are more reachable once you missed them the first twenty times. :)

[Gregory Blake · Rating 5 out of 5]

More so than even in the first volume of the series, this is a math-forward approach to Computer Science. I enjoyed the theory on psuedorandom number series, and the early parts of arithmetic, but got lost during the coverage of polynomial series and matrices. Knuth's treatment of his subject matter is (as expected) almost painfully thorough.

If you're a programmer with limited mathematical background, I strongly advise reviewing college algebra, pre-calculus, and calculus prior to reading this book.

[Arun Rajappa · Rating 5 out of 5]

Difficult, instructive, intelligent, amusing and brain-numbing - all rolled-in-to-one in this classic of CS. Buy it, read a page at a sitting and savor it - this is a book read over 5 years.

[Topilno]

Creating Web Pages for Dummies

[Linda Friedman · Rating 1 out of 5]

didn't really read this volume. :)