Kindle Notes & Highlights

I first learned the “Rule of 72” in a course on accounting. Assume that you invest a sum of money for y years at an interest rate of r percent per year. The financial version of the rule says that if r×y = 72, then your money will roughly double. The approximation is quite accurate: investing $1000 at 6 percent interest for 12 years gives $2012, and $1000 at 8 percent for 9 years gives $1999. The Rule of 72 is handy for estimating the growth of any exponential process. If a bacterial colony in a dish grows at the rate of three percent per hour, then it doubles in size every day. And doubling
...more

This highlight has been truncated due to consecutive passage length restrictions.

half a percent, π seconds is a nanocentury. Because the exponential program takes 107 seconds, we should be prepared to wait about four months.

But before placing too much confidence in a twenty percent margin of error, consider Vic Vyssotsky’s advice from a talk he has given on several occasions. “Most of you”, says Vyssotsky, “probably recall pictures of ‘Galloping Gertie’, the Tacoma Narrows Bridge which tore itself apart in a windstorm in 1940. Well, suspension bridges had been ripping themselves apart that way for eighty years or so before Galloping Gertie. It’s an aerodynamic lift phenomenon, and to do a proper engineering calculation of the forces, which involve drastic nonlinearities, you have to use the mathematics and
...more

This highlight has been truncated due to consecutive passage length restrictions.

almost unique. “When Roebling was asked whether his proposed bridge wouldn’t collapse like so many others, he said, ‘No, because I designed it six times as strong as it needs to be, to prevent that from happening.’ “Roebling was a good engineer, and he built a good bridge, by employing a huge safety factor to compensate for his ignorance. Do we do that? I submit to you that in calculating performance of our real-time software systems we ought to derate them by a factor of two, or four, or six, to compensate for our ignorance. In making reliability/availability commitments, we ought to stay back from the objectives we think we can meet by a factor of ten, to compensate for our ignorance. In estimating size and cost and schedule, we should be conservative by a factor of two or four to compensate for our ignorance. We should design the way John Roebling did, and not the way his contemporaries did — so far as I know, none of the suspension bridges built by Roebling’s contemporaries in the United States still stands, and a quarter of all the bridges of any type built in the U.S. in the 1870’s collapsed within ten years of their construction. “Are we engineers, like John Roebling? I wonder.”

Chris Van Wyk and I chatted about code tuning early one afternoon; he then wandered off to improve a C program. A few hours later, he had halved the run time of a three-thousand line graphics program. Although the run time for typical images was much shorter, the program took ten minutes to process some complicated pictures. Van Wyk’s first step was to profile the program to find how much time was spent in each function (a profile of a similar, but smaller, program is shown on the next page). Running the program on ten typical test pictures showed that it spent almost seventy percent of its
...more

This highlight has been truncated due to consecutive passage length restrictions.

invoking the general storage allocator; this reduced the total run time of his program to 45 percent of what it had been previously (so the storage allocator now took 30 percent of the total time). An additional benefit was that the reduced fragmentation of the modified allocator made more efficient use of main memory than the original allocator.

In the early 1980’s, Ken Thompson built a two-phase program that solves chess endgames for given configurations such as a King and two Bishops matched against a King and a Knight. (This program is distinct from the former world-computer-champion Belle chess machine developed by Thompson and Joe Condon.) The learning phase of the program computed the distance to checkmate for all possible chessboards (over the given set of four or five pieces) by working backwards from all possible checkmates; computer scientists will recognize this technique as dynamic programming, while chess experts know it
...more

This highlight has been truncated due to consecutive passage length restrictions.

records, which fit comfortably on a single (dedicated) disk. Even though Thompson knew there would be just one copy of his program, he had to squeeze the file onto one disk. Thompson exploited symmetry in data structures to reduce disk space by a factor of eight, which was critical for the success of his entire system. Squeezing space also reduced its run time: decreasing the number of positions examined in the endgame program reduced the time of its learning phase from many months to a few weeks.