Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972. Retyped and converted to html ('Web browser format) by Henry Baker, April, 1995.

FLOWS AND ITERATED FUNCTIONS

Previous Up Next

ITEM 126 (Schroeppel):

An analytic flow for Newton's method square root: 
                2
               X  + K
Define F(X) by ------ ; then
                2 X

                                         N                 N
                                        2                 2
                           (X + sqrt(K))   + (X - sqrt(K))
F(F(F(...(X)))) = sqrt(k)  ---------------------------------
                                         N                 N
                                        2                 2
                           (X + sqrt(K))   - (X - sqrt(K))

which = sqrt(K) (coth 2  (arccoth X/sqrt(K))).

ITEM 127 (Schroeppel):

P and Q are polynomials in X; when does P(Q(X)) = Q(P(X)) ? (That is, P composed with Q = Q composed with P.)

Known solutions are:

  1. Various linear things.
  2. X to different powers, sometimes multiplied by roots of 1.
  3. P and Q are each another polynomial R composed with itself different numbers of times.
  4. Solutions arising out of the flow of X^2 - 2, as follows:

    suppose X = Y + 1/Y, then Y^N + Y^-N can be written as a polynomial in X.

    For example, P = the expression for squares = X^2 - 2 (N = 2) and Q = the expression for cubes = X^3 - 3 X (N = 3)

  5. Replace X by Y-A, then add A to the original constants in both P and Q. For example, P = X^2 and Q = X^3, then P = 1 + (Y-1)^2 = Y^2 - 2 Y + 2 and Q = 1 + (Y-1)^3, then P(Q) = 1 + (Y-1)^6 = Q(P). Similarly, replacing X with A Y + B works.
  6. There are no more through degrees 3 and 4 (checked with Mathlab); but are there any more at all?

ITEM 128 (Schroeppel):

Figure 7. A map of the process n-> binary string -> interpret as radix -2, iterated. To convert a number to base -2:

(n + ...101010) XOR (...101010) (reversible).

ITEM 129 (Schroeppel):

PROBLEM: Given F(X) as a power series in X with constant term = 0, write the flow power series. 
FLOW sub ZERO = X
FLOW sub ONE = F(X)
FLOW sub TWO = F(F(X))
etc.
NOTE (Gosper): If we remove the restriction that F has a power series, the functions that satisfy an equation of the form F(F(X)) = sin X can be put into one-to-one correspondence with the set of all functions.

ITEM 130 (Salamin):

If F(X) = X^N, the P-th flow is X^N^P, which has a branch point if N^P is non-integer. Under the hypotheses of the previous problem, it is possible to find the power series coefficients for P rational, but there is no guarantee the series will converge.

PROBLEM: Is the flow interpolation unique? If it is not, what extra conditions are necessary to make it unique for natural cases like X^N ?

ITEM 131 (Schroeppel):

Taking any two numbers A and B, finding their arithmetic mean and their geometric mean, and using these means as a new A and B, this process, when repeated, will approach a limit which can be expressed in terms of elliptic integrals. (See PI section.)

ITEM 132 (Gosper): LOOP DETECTOR

If a function F maps a finite set into itself, then its flow must always be cyclic. If F is one step of a pseudorandom number generator, or the CDR operation on a self referent list, or any function where it is easy to supply former values as arguments, then there are easy ways to detect looping of the flow (Knuth, The Art of Computer Programming, volume 2, Seminumerical Algorithms, sec. 3.1, prob. 7, page 7). If, however, the process or iterated application of the function is inexorable, (i.e., there is no easy way to switch arguments to the function), then the following algorithm will detect repetition before the third occurrence of any value.

Set aside a table TAB(J), 0 <= J <= log 2 (Largest possible period). Let C = the number of time F has been applied, initially 0. Compare each new value of F for equality with those table entries which contain old values of F. These will be the first S entries, where S is the number of times C can be right shifted before becoming 0. No match means F hasn't been looping very long, so increment C and store this latest value of F into TAB(J), where J is the number of trailing zero bits in the binary of C. (The first 16 values of J are: 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ...; Eric Jensen calls this the RULER function.) A match with entry E means the loop length is 1 more than the low E+2 bits of C - 2^(E+1).

ITEM 133 (Schroeppel, Gosper, Henneman & Banks) (from Dana Scott?):

The "3N+1 problem" is iteratively replacing N by N/2 if N is even or by 3 N + 1 if N is odd. Known loops for N to fall into are:
  1. 1 the zero loop, 0 -> 0
  2. 2 a positive loop, 4 -> 2 -> 1 -> 4
  3. 3 three negative loops (equivalent to the 3N-1 problem with positive N)
In the range -10^8 < N < 6 * 10^7, all N fall into the above loops. Are there any other loops? Does N ever diverge to infinity?

ITEM 134 (Schroeppel, Gosper):

Let N be iteratively replaced by (FLATSIZE (LONGHAND N)), the number of letters in N written longhand (e.g., 69 -> SIXTY NINE -> 9 (10 counting blanks)). The process invariably loops at 4 = FOUR.

ITEM 135 (Gosper): The "C" Curve

A brilliant archeologist is photographing a strange drawing on the wall of a cave. He holds the camera upright for some shots, moves it, and turns it 90 degrees for the rest. When he sees is prints he is amazed to find one of them apparently taken with the camera turned 45 degrees. After a moment's reflection, he correctly concludes that it is merely a double exposure.

What was the drawing?

Answer: It is a cousin to both the dragon and snowflake curves (and arose as a bug in a spacefilling curve). It can be constructed as follows. Start with a line segment. Replace it with the two legs of the isosceles right triangle of which it is the hypotenuse. Repeat this for the two new segments, always bulging outward in the same direction. We now have four segments forming half a square, with the middle two segments collinear. Replacing these four segments with eight and then sixteen, we find the middle two segments superimposed. As the process continues, the curve crosses itself more and more often, eventually taking on the shape of a wildly curly letter C which forms the envelope of a myriad of epicyclic octagons.

A faster way to approach the same limiting curve is to substitute the curve itself for each of its 2^2^n segments, starting with a 90 degree "<".

Yet another way to construct it is to iteratively connect opposite ends of two copies at a 90 degree angle. (The archeologist did this with his double exposure.) If we reduce the scale by sqrt(2) each time, the distance between the endpoints stays the same. If the initial line segment is red and there is some other blue shape elsewhere in the picture, the iteration will simultaneously proliferate and shrink the blue shapes, until they are all piled up along the red "C". Thus, no matter what you start with, you eventually get something that looks like the "C" curve.

There are other pictures besides the C curve which are preserved by this process, but they are of infinite size. You can get them by starting with anything and running the iteration backwards as well as forwards, superimposing all the results. A backward step consists of rotating the two copies in directions opposite those in the forward step and stretching by sqrt(2) instead of shrinking. David silver has sketched an arrangement of mirrors which might do this to a real scene.

Figure 8. Two orders of the "C" curve.

Previous Up Next