Posts

We wish to show that for small $x$, $$\sqrt{1+x} \approx 1 + \frac{x}{2}$$ To derive this formula, we use the well known fact that $$(1+x)^\alpha = \sum_{n=0}^\infty \frac{x^n}{n!} \prod_{k=0}^{n-1} (\alpha - k)$$ The result follows by substituting $\alpha = 1/2$ and truncating the series after two terms.

I gave a talk a USF a while back for the Special Lecture Series in Computer Science. The goal was to try to give a flavor for the intuition behind simulation algorithms. I’m not sure I succeeded in doing this coherently, but good practice for the next time.

Here are the slides, in pdf and keynote form. Caution: they are not very self-contained.

Say you want to flip a perfect coin, but the only coins available are imperfect. First, let’s consider the case where we don’t know the details of the available coins, and would prefer not to measure them. The simplest strategy is to flip a bunch of coins and determine whether the total number of heads is even or odd. As long as there’s a reasonable number of both heads and tails, the probability of an even number of heads will be close to one half.

Imagine that you throw a ball in the air, and lands on the ground and stops (i.e., the collision is inelastic). What happened to the energy and momentum? The answer for energy is completely different from that for momentum, which is a trivial but interesting illustration of the differences between them. Also we get fun with infinities. Assume a ball of mass $m$ and velocity $v$ hits the ground and stops.

Currently, we (or at least I) don’t know how to do multigrid on general problems, so we’re stuck using conjugate gradient. The problem with conjugate gradient is that it is fundamentally about linear systems: given $Ax = b$, construct the Krylov subspace $b, Ax, A^2 x, \ldots$ and pick out the best available linear combination. It’s all in terms of linear spaces. Interesting human scale physics is mostly not about linear spaces: it’s about half-linear subspaces, or linear spaces with inequality constraints.

A few days ago I was in another discussion where someone raised the question of why presidential elections are so close. In the interests of avoiding these discussions in future, here’s a histogram of the popular vote margin over all presidential elections (data from [1]):

Conclusion: presidential elections aren’t very close, and we should stop looking for explanations of why they are.

Here’s a combinatorial problem I found recently: given a 100 story building and two identical plates, what is the worst case number of drops required to determine the lower floor from which the plates break when dropped (if a plate drops and does not break, it is undamaged). The answer is 14, which I’ll state without proof. In the interest of completely useless generalization, we can ask what happens if we add more plates.

Here’s an interesting short paper by Wadler: Lazy vs. strict. Philip Wadler. ACM Computing Surveys, June 1996. To paraphrase, the simplest model of lazy evaluation is given by Church’s original $\lambda$ calculus, and the simplest model of strict evaluation is given by Plotkin’s $\lambda_v$ calculus. $\lambda$ is problematic because it gives a poor notion of the cost of programs, and $\lambda_v$ is problematic because it is not complete. These flaws can be removed at the cost of slightly more complicated models, and the resulting models turn out to be extremely similar.

Something just occurred to me about the gcc implementation of std::vector in C++. Internally, an instance of vector needs to store (1) a pointer to the start of the memory, (2) the current vector size, and (3) the current buffer size. However, (2) and (3) can be represented either as integers relative to the start pointer or as absolute pointers past the end of the active and buffer spaces. Specifically, the two representations are

Gah. I’m trying to write some straightforward combinatorial code in Haskell, and I finally got to the point where I had to start using nontrivial algorithms to make it acceptably fast. When I run those algorithms the first time, I get the following gem: *Main> drops 100 2 *** Exception: divide by zero The “drops” function is now 15 lines of mutually recursive Haskell, and the interactive interpreter conveniently informs me that there was a division by zero.