Wiggle paradox

Sometimes a graph looks wiggly because it’s actually quite flat.

This isn’t much of a paradox; the resolution is quite simple. A graph may look wiggly because the scale is wrong. If the graph is flat, graphing software may automatically choose narrow vertical range, accentuating noise in the graph. I haven’t heard a name for this, though I imagine someone has given it a name.

Here’s an extreme example. The following graph was produced by the Mathematica command Plot[Gamma[x+1] - x Gamma[x], {x, 0, 1}].

This is unsettling the first time you run into it, until you notice the vertical scale. In theory, Γ(x + 1) and x Γ(x) are exactly equal. In practice, a computer returns slightly different values for the two functions for some arguments. The differences are on the order of 10-15, the limit of floating point precision. Mathematica looks at the range of the function being plotted and picks the default vertical scaling accordingly.

In the example above, the vertical scale is 15 orders of magnitude smaller than the horizontal scale. The line is smooth as glass. Actually, it’s much smoother than glass. An angstrom is only 10 orders of magnitude smaller than a meter, so you wouldn’t have to look at glass under nearly as much magnification before you see individual atoms. At a much grosser scale you’d see imperfections in the glass.

The graph above is so jagged that it demands our attention. When the horizontal axis is closer to the proper scale, say off by a factor of 5 or 10, the problem can be more subtle. Here’s an example that I ran across yesterday.

The curves look awfully jagged, but this is just simulation noise. The function values are probabilities, and when viewed on a scale of probabilities the curves look unremarkable.

Rule of the last inch

From The First Circle by Alexander Solzhenitsyn:

Now listen to the rule of the last inch. The realm of the last inch. The job is almost finished, the goal almost attained, everything possible seems to have been achieved, every difficulty overcome — and yet the quality is just not there. The work needs more finish, perhaps further research. In that moment of weariness and self-satisfaction, the temptation is greatest to give up, not to strive for the peak of quality. That’s the realm of the last inch — here, the work is very, very complex, but it’s also particularly valuable because it’s done with the most perfect means. The rule of the last inch is simply this — not to leave it undone. And not to put it off — because otherwise your mind loses touch with that realm. And not to mind how much time you spend on it, because the aim is not to finish the job quickly, but to reach perfection.

Via Still I Am One

It can be hard to know when something deserves the kind of polish Solzhenitsyn talks about. Sometimes you’re in the realm of rapidly diminishing return and it’s time to move on. Other times, the finishing touches are everything.

Related post:

Scripting and the last mile problem

Speeding up simulation with recurrence relation

Last week I wrote about how memoization reduced a simulation’s execution time from 300 hours down to 38 minutes. This weekend I came up with a different approach that reduces the time down to 21 minutes by taking advantage of a recurrence relation.

The most expensive function in the simulation has four integer arguments. Each time the function is called, one of the arguments is incremented by 1. A random process determines which argument is incremented each time. This function has a set of recurrence relations that make it faster to calculate a new value if you have a previously computed value for adjacent arguments.

The recurrence relation approach is about 100x faster than the memoization approach for small runs. However, the time per run with memoization decreases with each run. The longer it runs, the more values it caches, and so the greater the chances that a value has already been computed. In the end, the recurrence relation is about 2x faster than the memoization approach. With an even larger run, I suspect the time for the two approaches would be roughly equal.

The new approach is faster, but it was more work to implement, and it depends critically on the assumption that consecutive arguments differ only by one increment of one argument.

Related post:

20 weeks down to 20 minutes

Twenty weeks down to twenty minutes

I had a simulation this week that I estimated would take 20 weeks to run. This estimate was based on too small a run. A more reliable estimate based on a longer run was 300 CPU hours, about two weeks running on a single processor. Before I split the problem up to run in parallel, I wanted to see if I could make each thread run faster.

The most expensive part of the simulation is a function that takes in four integer parameters and does a numerical integration. Each parameter could be any value from 0 to 120. So in principle there are 121^4 = 214,358,881 possible parameter combinations. I knew that some of these combinations were extremely unlikely or impossible, so I thought I could reduce the execution time by caching the most commonly called parameters. Maybe a few thousand arguments would account for most of the function calls.

I saved the function arguments and computed values in map, a.k.a. dictionary, associative array, etc. (The buzz word for this is memoization.) I set a maximum size on the map because I thought it could grow very large. Even if, say, a thousand arguments accounted for most of the function calls, maybe there were many more that only appeared once.

It turned out that the function was only called with 408 distinct parameter combinations. That means the same integrals were being evaluated millions of times. Caching these values reduced the execution time by a factor of about 800. In other words, the software could retrieve a previously computed value 800x faster than compute it from scratch.

The simulation that would have taken 300 hours took only 22 minutes, and so there was no need to make it run in parallel.

Update: I found a bug in my hashing algorithm. After fixing the bug, the time to run my simulations increased to 38 minutes. So my speed-up was a about a factor of 420 rather than 800, but still enough to run on one thread over lunch. The number of distinct arguments to the numerical integration was much more than 408 in the corrected program, but still small enough to cache.

The most brutal man page

In The Linux Command Line, the author describes the bash man page* as “the most brutal man page of them all.”

Many man pages are hard to read, but I think that the grand prize for difficulty has to go to the man page for bash. As I was doing my research for this book, I gave it a careful review to ensure that I was covering most of its topics. When printed, it’s over 80 pages long and extremely dense, and its structure makes absolutely no sense to a new user.

On the other hand, it is very accurate and concise, as well as being extremely complete. So check it out if you dare, and look forward to the day when you can read it and it all makes sense.

* If you’re not familiar with Unix lingo, “man” stands for “manual”. Man pages are online documentation.

Related post:

Review of The Linux Command Line

Review: The Linux Command Line

No Starch Press recently released The Linux Command Line: A Complete Introduction by William E. Shotts, Jr.

True to its name, the book is about using Linux from command line. It’s not an encyclopedia of Linux. It doesn’t explain how to install Linux, doesn’t go into system APIs, and says little about how to administer Linux. At the same time, the book is broader than just a book on bash. It’s about how to “live” at the command line.

The introduction explains the intended audience.

This book is for Linux users who have migrated from other platforms. Most likely you are a “power user” of some version of Microsoft Windows.

The book has a conversational style, explaining the motivation behind ways of working as well as providing technical detail. It includes small but very useful suggestions along the way, the kinds of tips you’d pick up from a friend but might not find in a book.

The book has four parts

  1. Learning the shell
  2. Configuration and the environment
  3. Common tasks and essential tools
  4. Writing shell scripts

The book could have just included the first three sections; the forth part is a bit more specialized than the others. If you’d prefer, think of the book has having three parts, plus a lengthy appendix on shell scripting.

The Linux Command Line is pleasant to read. It has a light tone, while also getting down to business.

Related post:

Perverse hipster desire for retro-computing

Boundary conditions are the hard part

What we call “differential equations” are usually not just differential equations. They also have associated initial conditions or boundary conditions.

With ordinary differential equations (ODEs), the initial conditions are often an afterthought. First you find a full set of solutions, then you plug in initial conditions to get a specific solution.

Partial differential equations (PDEs) have boundary conditions (and maybe initial conditions too). Since people typically learn ODEs first, they come to PDEs expecting boundary values to play a role analogous to ODEs. In a very limited sense they do, but in general boundary values are quite different.

The hard part about PDEs is not the PDEs themselves; the hard part is the boundary conditions. Finding solutions to differential equations in the interior of a domain is easy compared to making the equations have the specified behavior on the boundary.

No model can take everything into account. You have to draw some box around that part of the world that you’re going to model and specify what happens when your imaginary box meets the rest of the universe. That’s the hard part.

Related posts:

Three views of differential equations
Nonlinear is not a hypothesis
Approximating a solution that does not exist

What do colleges sell?

Universities are starting to give away their content online, while they still charge tens of thousands of dollars a year to attend. Just what are they selling? Credentials, accountability, and feedback.

Some people are asking why go to college when you can download a college education via iTunes U.

First, you would have no credentials when you’re done.

Second, you almost certainly would not put in the same amount of work as a college student without someone to pace you through the material and to provide external motivation. You’d be less likely to struggle through anything you found difficult or uninteresting.

Third, you’d have no feedback to know whether you’re really learning what you think you’re learning.

The people that I hear gush about online education opportunities are well-educated, successful, and ambitious. They may be less concerned about credentials either because they are intrinsically motivated or because they already have enough credentials. And because of their ambition, they need less accountability. They may need less feedback or are resourceful enough to seek out alternative channels for feedback, such as online forums. Resources such iTunes U and The Teaching Company are a godsend to such people. But that doesn’t mean that a typical teenager would make as much of the same opportunities.

Grokking electricity

After I finished an electromagnetism course in college, I said that one day I’d go back and really understand the subject. Now I’m starting to do that. I want to understand theory and practical applications, from Maxwell’s equations to Radio Shack.

I’m starting by reading the Feynman lectures on E&M. After that I plan to read something on electronics. If you have resources you recommend, please let me know.

I’ve started new Twitter account, @GrokEM. I figure that tweeting about E&M will help me stick to my goal. My other Twitter accounts post on a regular schedule (plus a few extras) and are scheduled weeks in advance. GrokEM will be more erratic, at least for now. (In case you’re not familiar with grok, it’s a slang for knowing something thoroughly and intuitively.)

Here’s what Feynman said about mathematicians learning physics, particularly E&M.

Mathematicians, or people who have very mathematical minds, are often led astray when “studying” physics because they loose sight of the physics. They say: “Look, these differential equations — the Maxwell equations — are all there is to electrodynamics … if I understand them mathematically inside out, I will understand the physics inside out.” Only it doesn’t work that way. … They fail because the actual physical situations in the real world are so complicated that it is necessary to have a much broader understanding of the equations. … A physical understanding is a completely unmathematical, imprecise, and inexact thing, but absolutely necessary for a physicist.

Heinlein coined grok around the same time that Feynman made the above remarks. Otherwise, Feynman might have said that only studying differential equations is not the way to grok electrodynamics.

Related posts:

What it means to understand an equation
Most important event of the 19th century

Oscillating Fibonacci ratios

You may know that ratios of consecutive Fibonacci numbers tend to the golden ratio in the limit. But do know how they tend to the limit? The ratio oscillates, one above the golden ratio, the next below, each getting closer. The plot shows F(n+1) / F(n) where F(n) is the nth Fibonacci number. The height of the horizontal line is the golden ratio.

plot

We can prove that the ratio oscillates by starting with the formula

F(n) = frac{ phi^n - (-1)^n phi^{-n} }{ sqrt{5} }

where φ = (1 + √5)/2 is the golden ratio.

From there we can work out that

frac{F(n+1)}{F(n)} - phi = (-1)^n frac{ phi + phi^{-1}}{phi^{2n} + (-1)^{n+1}}

This shows that when n is odd, F(n+1) / F(n) is below the golden ratio and when n is even it is above. It also shows that the absolute error in approximating the golden ratio by F(n+1) / F(n) goes down by a factor of about φ2 each time n increases by 1.

Related posts:

Honeybee genealogy
Fibonacci numbers at work
Breastfeeding and the golden ratio

Rushing to see numbers

Scientific programmers and algebra students start out with analogous bad habits.

Beginning algebra students rush to enter numbers into a calculator. They find it comforting to reduce expressions to floating point numbers as frequently as possible. This is understandable, but it’s a habit they need to break for numerous reasons: it’s more work, harder for a grader to follow, less accurate, etc. Better to do as much calculation as possible with symbols, then stick in numbers at the end.

A similar phenomena happens in scientific programming. We’re anxious to see numbers, so we print out numbers as soon as we produce them. There’s a tendency to sprinkle code with printf statements, then write scripts to scrape text output to gather results.

It’s better to keep numbers in data structures as long as possible, then dump the data to text as the last step. Why? For one thing, the output format might change: instead of a text dump, maybe you’ll want to put the data in a database or format it as an HTML table. More importantly, the “last step” will often change. What was the last step now becomes the next-to-last step because you think of something else to do. So you do more with the data in memory before producing output, rather than scraping the text output.

I quickly learned to delay plugging numbers into algebraic expressions. It took me longer to learn not to output numeric results until the last moment.

Funny and serious

G. K. Chesterton on being funny and being serious:

Mr. McCabe thinks that I am not serious but only funny, because Mr. McCabe thinks that funny is the opposite of serious. Funny is the opposite of not funny, and of nothing else. … Whether a man chooses to tell the truth in long sentences or short jokes is a problem analogous to whether he chooses to tell the truth in French or German. Whether a man preaches his gospel grotesquely or gravely is merely like the question of whether he preaches it in prose or verse. … The truth is, as I have said, that in this sense the two qualities of fun and seriousness have nothing whatever to do with each other, they are no more comparable than black and triangular.

Emphasis added. From Heretics. Text available online from Project Gutenberg.