Reflections on another year of reading Knuth
Almost a year ago, I posted a semi-review,
semi-rumination on the
first volume of Donald Knuth's classic computer science set, "The Art of Computer Programming".
I enjoyed reading it thoroughly enough that there was no question in my mind at the time that
I would go on to read volume 2. Having started volume 2 immediately after finishing volume 1, I
finally did complete it earlier this month. Now that I've finished volume 2, there's no doubt
in my mind that I'll go on to read volume 3, and anything else written by Knuth that I can get
my hands on.
If you're not familiar with the series, it's a very academic (but still surprisingly readable)
treatment of many of the fundamentals of computer science. Being written by an academic, for
academic purposes, each section is rounded out with a series of exercises that were written to
solidify the concepts of the section in your mind. Knuth's exercises are notoriously difficult —
most of them require you to re-read sections of the book and if you want to solve most of them, you'll have to have a pencil
and paper handy, along with a lot of focused concentration. Just as I did with volume 1, I attempted every
single exercise. For some (now unfathomable) reason I had it in my head that volume 2 would be
easier going than volume 1, but as I discovered, volume 1 was just the warm-up.
Volume 2 consists of just two
chapters (chapters 3 and 4 of the overall work). The first chapter of this book, chapter 3, is all about
random number generation. You might not think that the topic of random number generation would be
able to fill up even fifty pages, let alone the nearly 200 that Knuth dedicates to it, but you'd
be mistaken. He starts off by developing a detailed mathematical theory on what "randomness"
really means and then goes on to discuss five different ways to test randomness. It had
never occurred to me that randomness is something that you even could test, but Knuth shows you
how you can apply sophisticated statistical methods to random number generators to test just how random they are.
Chapter 4 discusses what he calls arbitrary-precision arithmetic. This includes a deep, deep
discussion of floating-point arithmetic as well as high-precision multiplication and
modulus operations. Both of these topics were fascinating for me - I spent a lot of time
researching both while I was writing Implementing SSL; random-number generation and high-
precision arithmetic are two of the most important topics in cryptography, and crucial to get
right. Although I considered myself very well-versed on both topics, Knuth had a lot to
teach me. For instance, I stated in my own book, without proof,
that the fastest way to exponentiate a number was the "square-and-multiply" method — Knuth
admonishes authors who state without proof that this is the fastest way to exponentiate numbers
and demonstrates (as only he can) that it actually isn't! If you're curious, I'll refer you to
section 4.6.3.
The exercises in this book were, subjectively, harder than those in the first volume. I think that
this is in part because volume 1 was meant to be a bit more "introductory" and also because the
material is more mathematical. As always, Knuth doesn't waste any time with "easy" questions,
but instead challenges you to understand the material on a more fundamental level than just reading over
it, however carefully, could ever hope to provide. As I did with volume 1, I made a genuine effort to solve
each and every exercise in the book other than the "unsolved computer science research problems"
(maybe I'll go back to those some day).
One thing that puts a lot of people off of TAOCP is Knuth's use of MIX assembler to generate examples.
Although I think those people are missing out on a lot of the nuance of the series by skipping
over the MIX assembler parts, they will be happy to note that there's really not too much
programming in volume 2; it's almost all mathematical theory. I don't remember there being more
than one or two programming exercises in this volume. Most of the exercises were heavy math.
He calls for a lot of proofs - in many cases I satisfied myself with working a few examples to convince
myself that what he wanted to see proven was actually true, stopping short of trying to produce a
publication-worthy rigorous mathematical proof. As I said before, don't judge me until you try
it yourself.
I've seen it suggested that this series of books is interesting only from a historical perspective
and has been been supplanted by better, more modern, more up-to-date treatments like Sedgewick's
or CLRS.
I've read CLRS (Cormen, Leiserson, Rivest and Stein's "Introduction to Algorithms") carefully
as it was my graduate algorithm's course textbook, and quite a bit of Sedgewick's "Algorithms"
(since it was undergraduate algorithm's course textbook), and I don't really see that there's
a lot of overlap between these sets of books. Of course, any book on algorithms will discuss
sorting algorithms and things like red-black trees, but CLRS is more focused on complex algorithms
like Djikstra's algorithm and the max-flow/min-cut algorithm, which would almost be out of place
in TAOCP. Neither CLRS nor Sedgewick spend any time discussing how floating-point arithmetic
is implemented on a real computer or how to maximize the period of a linear congruential random
number generator. TAOCP is a lot lower-level than the more contemporary algorithms books —
I'd suggest that any serious developer should read them all.
Add a comment:Completely off-topic or spam comments will be removed at the discretion of the moderator. You may preserve formatting (e.g. a code sample) by indenting with four spaces preceding the formatted line(s) |
I'm the author of the book
"Implementing SSL/TLS Using Cryptography and PKI".
Like the title says, this is a from-the-ground-up examination
of the SSL protocol that provides security, integrity and
privacy to most application-level internet protocols, most notably HTTP.
I include the
source
code to a complete working SSL implementation,
including the most popular cryptographic algorithms
(DES, 3DES, RC4, AES, RSA, DSA, Diffie-Hellman, HMAC, MD5, SHA-1,
SHA-256, and ECC), and show how they all fit together
to provide transport-layer security.
Joshua Davies
Past Posts
- April 30, 2021: A Date Picker Control in Vanilla Javascript
- March 31, 2021: A Web Admin Console for Redis, Part Three
- January 27, 2021: A Web Admin Console for Redis, Part Two
- December 21, 2020: A Web Admin Console for Redis, Part One
- November 30, 2020: What is Procmail and why is it using up all my memory?
- September 30, 2020: Minimal Drag and Drop Support in Javascript
- August 31, 2020: Covariance and Contravariance in Generic Types
- July 31, 2020: How Spread Out Are the Floating Point Numbers?
- June 25, 2020: ERD Diagramming Tool, Part Three
- April 30, 2020: ERD Diagramming Tool, Part Two
- March 31, 2020: ERD Diagramming Tool, Part One
- February 28, 2020: MathJax and "t.setAttribute is not a function"
- December 30, 2019: Solving Systems of Equations with Python
- October 30, 2019: Linear Regression with and without numpy
- September 30, 2019: Reading a Parquet file outside of Spark
- August 30, 2019: UML Diagrams with MetaUML
- July 30, 2019: Clustering in Python
- June 25, 2019: A Walkthrough of a TLS 1.3 Handhsake
- May 31, 2019: A DataType Printer in Java
- April 30, 2019: A Simple HTTP Server in Java, Part 3 - Cookies and Keep Alives
- March 28, 2019: A Simple HTTP Server in Java, Part 2 - POST and SSL
- February 28, 2019: A Simple HTTP Server in Java
- January 29, 2019: Angular CLI Behind the Scenes, Part Two
- September 30, 2018: Angular CLI Behind the Scenes, Part One
- August 31, 2018: Into the MMIX MOR Instruction
- July 24, 2018: Undoing Percentage Changes in your Head
- June 30, 2018: Generating Langford Pairs in Scala
- May 25, 2018: Reflections on Three Years of Reading Knuth
- April 30, 2018: java.lang.NoSuchMethodError: org.junit.vintage. engine.descriptor.RunnerTestDescriptor. getAllDescendants
- March 30, 2018: An Excel Spreadsheet for the Academy Awards
- February 28, 2018: Git for Subversion Users
- January 31, 2018: The Evolution of AngularJS
- December 31, 2017: Numerical Integration in Python
- October 31, 2017: Gradle for Java Developers
- September 29, 2017: Reflections on another year of reading Knuth
- August 30, 2017: SSL OCSP Exchange
- July 27, 2017: A walk-through of an SSL certificate exchange
- June 30, 2017: A walk-through of an SSL key exchange
- May 31, 2017: A walk-through of the SSL handshake
- March 31, 2017: A walk-through of the TCP handshake
- February 28, 2017: The TLS Handshake at a High Level
- January 31, 2017: A Walk-through of a JWT Verification
- August 31, 2016: Reflections on a year of reading Knuth
- July 29, 2016: Matching a private key to a public key
- June 30, 2016: A Completely Dissected GZIP File
- May 31, 2016: Automatic Guitar Tablature Generator, Part 2
- April 28, 2016: Automatic Guitar Tablature Generator, Part 1
- March 31, 2016: Import an encrypted private key into a Java Key Store
- February 26, 2016: Import a private key into a Java Key Store
- January 31, 2016: Debian Linux on MacBook Pro
- December 29, 2015: Is Computer Science necessary or useful for programmers?
- November 30, 2015: Client certificate authentication vs. password authentication
- October 28, 2015: A Utility for Viewing Java Keystore Contents
- September 29, 2015: Debugging jQuery with Chrome's Developer Tools
- August 26, 2015: Getting Perl, MySQL and Apache to all work together on Mac OS/X
- July 30, 2015: Extract certificates from Java Key Stores for use by CURL
- June 29, 2015: Using the Chrome web developer tools, Part 9: The Console Tab
- May 28, 2015: Using the Chrome web developer tools, Part 8: The Audits Tab
- April 30, 2015: Using the Chrome web developer tools, Part 7: The Resources Tab
- March 30, 2015: Using the Chrome web developer tools, Part 6: The Memory Profiler Tab
- February 27, 2015: Using the Chrome web developer tools, Part 5: The CPU Profiler Tab
- January 31, 2015: Using the Chrome web developer tools, Part 4: The Timeline Tab
- December 31, 2014: Using the Chrome web developer tools, Part 3: The Sources Tab
- October 31, 2014: Using the Chrome web developer tools, Part 2: The Network Tab
- September 30, 2014: Using the Chrome web developer tools, Part 1: The Elements Tab
- August 11, 2014: Unable to find valid certification path to requested target
- June 30, 2014: Sort by a Hierarchy
- May 29, 2014: OpenSSL Tips and Tricks
- April 25, 2014: Heartbleed: What the Heck Happened
- February 28, 2014: Replace Microsoft Money with a Spreadsheet
- January 29, 2014: An Illustrated Guide to the BEAST Attack
- December 21, 2013: Where does GCC look to find its header files?
- October 24, 2013: Planning a Subversion import
- August 28, 2013: Compile and test an iOS app from the command line
- July 31, 2013: The Hidden Costs of Software Reuse
- June 26, 2013: Beware of mvn war:inplace
- May 29, 2013: Block Font Design Using Javascript
- April 4, 2013: Parsing a POM file using only SED
- February 22, 2013: Inside the PDF File Format
- December 31, 2012:How and why rotation matrices work
- November 27, 2012:Date Management in Java
- October 21, 2012:
Installing Debian Without a Network
- August 14, 2012:
My Review of Matt Neuburg's "Programming iOS 5"
- July 16, 2012:
An example OAuth 1.0 Handshake and mini-library
- May 23, 2012:
A Javascript one-liner to display cookie values
- April 27, 2012:
How SSL Certificates Use Digital Signatures
- March 29, 2012:
A breakdown of a GIF decoder
- February 15, 2012:
The design and implementation of LZW (the GIF compression algorithm)
- January 16, 2012:
Calculate the day of week of any date... in your head
- December 4, 2011:
Understanding CRC32
- October 29, 2011:
Efficient Huffman Decoding
- October 4, 2011:
Extract a private key from a Gnu Keyring file
- September 5, 2011:
From Make to Ant to Maven
- July 18, 2011:
A bottom-up look at the Apache configuration file
- July 6, 2011:
Fun with the HTML 5 Canvas Tag
- Jun 16, 2011:
Pain and disfiguration upon all comment spammers
- May 31, 2011:
Use of RSSI and Time-of-Flight Wireless Signal Characteristics for Location Tracking
- May 7, 2011: Implementing SSL
- Apr 24, 2011: Dissecting the GZIP format
|
As to you, kudos for admitting an error in your book. That's what I call intellectual integrity, something which is getting more and more rare. Again, I really enjoy this little blog. Hope your JavaScript date picker won't be the last we hear of you.