The Pendulum and the Winch

I often find that explaining computer science to non-computer-scientists is difficult.  It's been said that computer science is like no other field of study.  Well, I think that's a rather strong claim to make.  What follows is a translation of a standard problem in computer science into physics.  It is an analogy, unrealistic but nevertheless interesting.

I have a pendulum, supported by some apparatus ultimately connected to a pillar or pole.  It is possible to move the apparatus up or down, but only by manually detaching and reattaching it by hand.  I have a winch affixed to this apparatus which may raise or lower the pendulum.  It is connected to a coil of rope or string (which, for the purposes of this problem, is infinitely long yet magically takes up a finite volume), and can be remotely controlled at the press of a button.  The winch is also geared discretely; it only turns in units, and then only one at a time.

I wish to carry out a series of experiments involving varying the length of my pendulum.  In particular, I often want to lengthen the pendulum.  Most of the time, this setup suits me quite well.  But sometimes, I find I need a pendulum longer than the apparatus is high off the ground.  In these situations, I need to climb the pillar and move the winch up.  In so doing, I may need to start an entire experiment over again because the pendulum lost energy while I was climbing.  How can I avoid or minimize those climbs in proportion to the maximum length of the pendulum?  We must assume I do not know the maximum length in advance, perhaps because my experiments are highly complex and difficult to predict, or perhaps because they are directed by someone else's instructions, and they did not think to tell me in advance how long a pendulum I would need.

The obvious answer is to fix the winch at the top of the pillar.  But we may suppose the pillar is quite tall.  In fact, it is extraordinarily tall, to the point that "pillar" is no longer an adequate term.  Instead, it is essentially a space elevator.  The logistical problems with this should be apparent, even if we suppose I also have a crane or cherry picker of equivalent (and grossly unrealistic) height.

We have encountered another constraint: we must minimize the height of the pendulum above the ground.  If the pendulum is too high, it will be more difficult to work with.  This is not a hard and harsh requirement; we may say that it is acceptable for the pendulum to get quite far off the ground, so long as its height remains reasonable in proportion to the maximum length of the pendulum.

The commonly accepted solution (on the other side of the analogy) is to double the height of the winch every time the pendulum touches the ground.  If we only lengthen, and never shorten, the pendulum will never be farther off the ground than it is long.  As we lengthen, the number of times we raise the winch is proportional to the binary logarithm of the pendulum's length, a nice and small number.  Of course, if we shorten the pendulum again, these metrics look worse, but we specified we only cared about them in proportion to the maximum length of the pendulum, not its current length.

Actually, the preferred solution multiplies the height of the winch by some smaller factor instead of doubling, because this works better in practice.  Different solutions use different factors, and there is some disagreement over the ideal value here.  But mathematically, 2 is an inferior choice.

If we say the cost of moving the winch is proportional to the current height of the winch, we may say that on average, lengthening the pendulum has a constant cost.  This means that on average, we expend the same amount of effort every time we lengthen the pendulum by a unit.  We can see this as follows: Every time we move the winch, we incur a cost proportional to the current length of the pendulum.  The previous winch-moving cost half as much as the current one, and so on.  By summing all of the preceding costs, we will arrive at a figure proportional to at most the height of the winch, which is the same as the cost we're about to pay.  That means the total paid is also proportional to the height of the winch, which is equal to the length of the pendulum (the pendulum is on the ground right now, since we're moving the winch), and so we see the total paid is proportional to the total lengthened.

As some of you may have guessed, the analogy is to a dynamic array, known to C++ developers as a vector.  The length of the pendulum is the size of the array, while the height of the winch is its capacity.  The height of the pendulum above the ground is the wasted memory which has been allocated but not consumed.  Lengthening is appending and shortening is popping.  Moving the winch is a reallocation.  The preceding paragraph is amortized analysis.  Under that analysis, we may also think of the height of the pendulum as the potential function, which meshes quite nicely with our analogy.