A calculus game. (Programming) Neil M. Wigley.
What happens if you keep repeating something? If you poke your sister in the arm enough times, she'll whack you. If you make enough obscene telephone calls to your neighbor, the police will surely get you. What if you apply a function y = f(x) (straight out of elementary calculus) to a number X, and get a number y; and then you apply f to y and get a new number f(f(x)) = f(y) and then you do the same thing again and again?
It is not an easy problem to solve mathematically, except in certain special cases; for example, if f(x) [is greater than or =] x always, then our numbers will get bigger and bigger. They may go off to infinity or they may slow down (converge) somewhere before.
Here we shall consider an elementary example which exhibits some rather exotic behavior. I first learned of this example in Scientific American .
In figure 1 we see a parabola and the diagonal line y = x. The height of the parabola is [lambda], where [lambda] is a number between 0 and 1; later we shall vary [lambda].
We start with a value of x, call it X.sub.0. Geometrically, what we do is start on the x-axis at X.sub.0, go up to the parabola, go to the right (left) till the diagonal line, then go up (down) to the parabola, then right (left) to the line, etc. The moving point thus describes a rectangular path. It is the shape of this path which can be so fascinating.
For small values of [lambda] (less than .75) the point describes a sequence of (almost) rectangles which get smaller and smaller, converging on a point (the point where the line crosses the parabola). For larger values of [lambda], the behavior of the path is chaotic; and for values of [lambda] in between the behavior is, likewise, in between: not chaotic, but not as well organized as for small [lambda].
The educational value of this game is a simple example of nonlinearity, a subject which is just beginning to earn some attention in the mathematical community. Thus observance of the paths described above can give a rudimentary view of a simple, yet chaotic, nonlinearity.
Let us now do some algebra, and find the equations we want to satisfy, so that we can write a program. We need the equation of the parabola. We want the parabola which opens down, goes through the points (0,0) and (1,0) on the x-axis, and has maximum height [lambda] above the point (.5,0) on the x-axis. We shall vary [lambda] later, but we insist that 0 [is less than or =] [lambda] [is less than or =] 1. It should not be a surprise that the equation is y = 4[lambda]x(1-x) which is obviously a parabola and gives y = 0 when x = 0 or 1, and, when x = .5, we see that y = [lambda]. This parabola also opens down, as desired.
Notice that when 0 [is less than or =] x [is less than or =] 1, we have 0 [is less than or =] y [is less than or =] 1, so that can't go leaping off to infinity. Moreover, f(y) is defined, and thus so is f(f(y)). We have thus defined a sequence, and maybe it will converge. The problem now is to compute what happens to an initial value of x, say x.sub.0, which we call the seed, after it has been hit with f through x.sub.1 = f(x.sub.0.), x.sub.2 = f(x.sub.1.), etc.
It would be boring and time-consuming to calculate these numbers and compare them after, say, 100 iterations. Let's try using the monitor to see if it can help us.
To see if what is happening on screen agrees with the algebra, we notice that any point on the diagonal line must be of the form (x,x), since y = x there. So we start with a seed x.sub.0 which we place at (x.sub.0.,0) on the x-axis. Then we go straight up to the parabola and meet it at a point with the same abscissa x.sub.0 and with ordinate y where y = f(x.sub.0.), which we call x.sub.1. To the right (or left) of this point is the point (y,y), which shares the same ordinate (height) and lies on the diagonal line. This point will have the same x-coordinate as it does y-coordinate, and the latter is the same as x.sub.1 = y = f(x.sub.0.). Therefore this point will have coordinates (x.sub.1,x.sub.1.).
Now we begin our loop. From here we go up (down) to the parabola, then over to the line, and now repeat. Thus it is curve-line-curve-line, etc. As the point moves on, it traces rectangular shapes, two of whose vertices are on the diagonal line.
The question now is what happens to these two vertices on the line after a million iterations. And the results are surprising: it depends a great deal on [lambda]! If [lambda] is small ([lambda] [is less than or =] .75) then things are boring; if [lambda] is greater than .75, things get exciting, and when [lambda] gets near enough to 1 things get absolutely chaotic! Around [lambda] = .8 there are some rather interesting patterns: rectangles within rectangles--like a hall of mirrors.
More mathematical details are available in the excellent article by Hofstadter. One new result is the existence of certain constants which seem to depend on the function (in our case, the parabola), but which in fact don't change if you change the function (e.g., a sine wave). These are called universal constants.
Listing 1 is the program as written for an Apple II+. Lines 2 to 100 are sub-routines. In lines 1010 to 1030 we define screen coordinates. Then the program begins, with the user selecting one of three functions, one of which is the parabola. Lines 1120 to 1210 plot the curve and the vertical line above the seed. Lines 1250-1310 represent the main do-loop. The menu begins on line 1320 and continues through line 1410.
On the menu are options: select a new lambda or new seed, change the function or quit, clear the screen (which could better have been called erase), and "enlarge," which is an attempt at magnification of the picture when the details get too small. It is with this feature that you can get the rectangles-within-rectangles patterns.
For a universal constant with your name on it, just copy the program, run it, and follow the dot. Happy staring!