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. Before it hits, it has energy $\frac{1}{2}m v^2$ and momentum $m v$. After it hits, the energy and momentum of the ball are both zero, so by conservation they must have gone elsewhere.

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. As we start cramming more complicated collision handling into algorithms, these inequalities play a larger and larger role in the behavior, and linearizing everything into a CG solve hurts.

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. Specifically, what is the cost $C(s)$ to analyze an $s$ story building if we can buy as many plates as we like? Say each plate costs as much as one drop.

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. Specifically, the only difference between them is the following law, let x = M in N -> N which holds with laziness and fails for strictness. In other words, the different between strict and lazy languages is exactly what one would expect: in a lazy model unused terms can be ignored, and in a strict model they must be evaluated to make sure they don’t loop forever.

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. No hint as to where it might be, of course. Come to think of it, this was probably the reason I dropped back to Python after my last Haskell stint.