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:
- Various linear things.
- X to different powers, sometimes multiplied by roots of 1.
- P and Q are each another polynomial R composed with itself different numbers
of times.
- 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)
- 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.
- 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 the zero loop, 0 -> 0
- 2 a positive loop, 4 -> 2 -> 1 -> 4
- 3 three negative loops
(equivalent to the 3N-1 problem with positive N)
- -2 -> -1 -> -2
- -5 -> -7 -> -10 -> -5
- -17 -> -25 -> -37 -> -55 -> -82 -> -41 -> -61 -> -91 -> -136 -> -68 -> -34 -> -17
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