
Iterative Functions and the HP48, Part 3    Revised version

Continuing Part 2's introductory look at iterative functions with some
HP48 demonstrators that are actually simple fractals.

                                        (c) Bill Markwick, May/99
                                            bd628@torfree.net


In the previous section, we looked at software that runs the HP48
display at 30 frames per second in 16 million colors. Did you miss that?
Hmm, well, you just can't trust the net any more. We'll have to continue
on with more about bifurcations and programs to generate miniature
fractals.


3.1 Feigenbaum and Bifurcation
------------------------------

Recall from the DOTS program that the Verhulst equation began to produce
two or more values consistently when u was around 3. The next program is
a considerable expansion on DOTS, and draws a picture called the
"bifurcation diagram" or "Feigenbaum diagram", the latter being named
after Mitchell Feigenbaum, a modern physicist who did considerable
research into the nature of bifurcating iterates (more on that later).
Its self-similar construction qualifies it as a fractal.

Tune up your imagination: the program FEIG begins at column zero of the
display. It runs the Verhulst iterator 10 times with no output to the
program, just to get over the initial period of instability. Then it
runs it again 64 times and plots the amplitude of the output(s) in
column zero. Now it steps to the next column of pixels and the value of
u is incremented (the increment sets the value of u at just below 3 to
just a hair more than 4). The expression is run again and any values
plotted.

Okay so far? What it displays is in effect the program DOTS running
vertically for each column, with u getting larger and larger as the
plot moves to the right; the result is that the expression's outputs
move through stability towards chaos. You're seeing the behavior of the
Verhulst function's iterates as we vary u, whereas in DOTS we looked at
the orbit of the iterates for a single fixed u.

Obviously this takes time - a full-screen display is good for over 7
minutes. I've compressed it into 67 columns, or about half a screen,
which takes about 3.8 minutes. There's some loss of detail, but then the
HP's LCD is fairly coarse to begin with.

I used .01 for the initial value X0. It isn't critical.

Starting at the left: we see a few dots peek out for about 10mm as u is
stepped from 2.75, indicating that the expression is in a stable region
and (it thinks) settling down. It's in for a surprise as the value of u
increases and the first bifurcation occurs.

You'll have to watch closely as the main fork begins bifurcating itself
- things happen rapidly as u climbs towards 4. The two branches each
split into two, and then those into two, and it quickly gets fairly
complicated as various n-cycles develop (see the discussion of u values
versus cycles in the DOTS section). This is known as a "period-doubling
cascade". (The initial doublings form a Cantor set, which we met in
Part 2. It's soon obscured as the cycling gets complicated.)

The crisscrossing bifurcations soon darken the screen, but it isn't
absolutely dark - note the blotches of clear space here and there. These
indicate areas of stability; the largest is a column of "white" at about
u = 3.8 - this is a series of stable 3-cycles (more obvious in the
full-screen version).

Self-similarity: one of the hallmarks of a fractal is that certain parts
of it seem to contain the whole in miniature if you zoom in.
Unfortunately you can't zoom FEIG (there's a rainy-day project for you
programmers), but imagine the image as two snow-capped mountain peaks
tipped sideways. If you zoomed in to either peak, you'd see a small
replica of the entire diagram. Not an exact replica, but similar. These
replicas continue on at an ever-decreasing scale.

Finally, u passes 4 and ends at 4.09; we see a few pixels protruding at
the top right of the screen. These are leftovers from iterations that
have escaped to infinity as chaos takes over the expression's outputs.


Program: FEIG   Half-screen bifurcation diagram   Execution time: 3.8 min.

%%HP: T(3)A(R)F(.);
\<< ERASE 2.75 \-> u       @ Erase PICT and start u at 2.75.
  \<< { # 0d # 0d }
PVIEW PICT { # 0d
# 0d }
"\<- U=2.75 U=4 \->" 1     @ Label PICT.
\->GROB REPL 0 66
    FOR x 1 10             @ Main loop for 67 columns.
      FOR A \-> X 'u*      @ Get X0; "waste" loop discards ten iterations
X*(1-X)'                   @ to avoid initial instability.
      NEXT 0 63
      FOR B \-> X 'u*      @ Run the Verhulst iterator and
X*(1-X)' DUP 63 *          @ draw pixel(s) corresponding to output(s).
64 SWAP -                  @ Make increasing values plot upwards.
R\->B x R\->B SWAP 2
\->LIST PIXON              @ Turn on required pixel.
      NEXT .02 'u'         @ Increment u by .02 and start over for
STO+                       @ the next column of pixels.
    NEXT DROP { }
PVIEW                      @ Press ON to exit graphics screen.
  \>>
\>>

  Stack:
  level 1: X0   (.01 works well)


3.2 The Full Montage
--------------------

For those with lots of time and batteries, the above can easily be
converted to full-screen. It takes about 7.6 minutes to display and
gives a *little* more detail (as good as 131 by 64 ever gets).

  1. Change the two occurrences of 2.75 at the beginning to 2.69.

  2. Change the 0 66 FOR to 0 130 FOR.

  3. Near the end, change NEXT .02 to NEXT .01.


3.3 Feigenbaum's Number
-----------------------

His number is 555-2107. Don't call until later because he's grouchy in
the morning. He'll tell you this: in the 70s, he was doing university
research into the way iterates bifurcate, and he noticed that there's a
pattern. You can see it in the display for the above program - the
distance between bifurcations gets smaller and smaller. The difference
turns out to be the previous distance divided by approximately 4.6 or
4.7. Feigenbaum showed in 1975 that taken to the limit (infinity), the
number is 4.6692016 plus a whole lot more decimal places. This is now
known as Feigenbaum's Constant - a new physical constant, and not just
because it occurs in the Verhulst expression. It turns up any time
there's period doubling of any kind.

There's also Feigenbaum's Point. Note that the display is roughly
divided into two sections, the simple curves and bifurcations, and the
sudden frenzy of activity that turns the screen dark. Feigenbaum derived
an exact point where this occurs, at u = 3.5699456. It's of more
interest mathematically than graphically.


3.4 Sierpinski's Gasket
-----------------------

Vaclav Sierpinski was a Polish mathematician who created some
interesting early-fractal geometric patterns around 1915. One of them is
now known as the Sierpinski Gasket, or Triangle, or Sieve.
Mathematicians are creative, but can't agree on names.

Drawing a Gasket is dead easy: start with an equilateral triangle. Join
the midpoints of the sides, forming four equilateral triangles inside
the main one. Leave the center triangle untouched, and repeat the
midpoint-joining sequence for the other three. Repeat over and over to
infinity, or until your pencil gets dull, whichever occurs first.

What you'll have is a great example of self-similarity, because the
pattern repeats itself forever in smaller and smaller triangles. As for
the name, well, if you had a triangular engine with a triangular
cylinder, I guess the head gasket would look something like that.

Here's a program to draw the Gasket. There are quite a few (rather
large) BASIC Gasket programs in fractal books, but the technique I chose
is wonderfully concise, and like so many ideas in this article, was
lifted from "Chaos and Fractals" (see References at the end).

The entire program can be reduced to "x AND y". As to why a simple AND
statement does all this, it's covered at great length in the book
(first brush up on your set theory). All the rest of it is just to
position the image. If you reduced the program to testing for x AND y
equalling zero and then just plotting x and y, you'd still get a
Sierpinski triangle, though it would be a skewed isosceles with one side
against the left side of the display.


Program: GASK   Draws Sierpinksi's Gasket   Execution time: 1.3 min.

%%HP: T(3)A(D)F(.);
\<< ERASE { # 0d # 0d       @ Set up graphic screen.
} PVIEW 0 63                @ Start vertical (column) loop.
  FOR Y 0 Y
    FOR X                   @ Start horizontal (row) loop.
      IF X R\->B DUP        @ Convert x and y to binary numbers, and
Y R\->B SWAP - AND          @ then AND x, y-x.
# 0d ==                     @ If the result is zero,
      THEN X 65 + Y         @ then turn on a pixel, with the coordinates
2 / - R\->B Y R\->B 2       @ adjusted to center the image and
\->LIST PIXON               @ make the triangle equilateral.
      END
    NEXT                    @ Step to the next position.
  NEXT { } PVIEW            @ Press ON to exit the graphics screen.
\>>

  Stack:
  No input required.


The Gasket is not just a curiousity - it turns up again and again in
various geometric constructions. There are also similar constructions,
such as Sierpinski's Carpet, which is a square containing a myriad of
little squares. A mindboggler is the Menger Sponge, which is six Carpets
in the form of a cube with the square holes running right through it;
taken to infinity, it ends up with a 3D shape but no real volume, sort
of like Rice Krispies or Puffed Wheat - theoretical cereals with shape
but no mass.

Here's one I discovered while tinkering. It runs for over three minutes,
so just cut it off with ON after you get the effect. I've never seen it
anywhere else, so I'm foolishly claiming it as original. I call it
Sierpinski's Wallpaper. Notification of knighthoods, Nobel Prizes, etc.,
can be sent by email.


Program: SWALL   Designs mathematician's wallpaper   Execution time: > 3 min.

%%HP: T(3)A(R)F(.);
\<< ERASE { # 0d # 0d
} PVIEW 0 63
  FOR Y 0 130
    FOR X X R\->B Y
R\->B OR Y R\->B 2
\->LIST PIXON
    NEXT
  NEXT { } PVIEW
\>>

  Stack:
  No input required.


3.5 Pascal's Triangle
---------------------

Pascal's Triangle, which predates Sierpinski's by about 250 years, is
composed of the coefficients resulting from the Binomial Theorem, which
is the expansion of (a+b)^n.

This program produces full algebraic expressions in a and b, given the
value of n.


Program: BNOM1   Expands (a+b)^n for any n   Execution time: varies with n

%%HP: T(3)A(D)F(.);
\<< \-> N '\GS(K=0,N,COMB
(N,K)*a^(N-K)*b^K)'
EVAL
\>>

  Stack:
  level 1: value of n

Enter a 2 and out comes 'a^2+2ab+b^2', although it only looks kewl if
you're using a stack replacement like Java or EQStk (or if you're
desperate enough to press View to use the Equation Writer). If you'd
prefer the expansion of (a+1), just delete the *b^K from the above.

And here's a version of the above that produces only the coefficients as
a list:


Program: BNOM2   Binomial coefficients   Execution time: varies with n

%%HP: T(3)A(D)F(.);
\<< \-> n
  \<< 0 n
    FOR K 'COMB(n,K
)' EVAL
    NEXT n 1 +
\->LIST
  \>>
\>>

  Stack:
  level 1: value of n


If you feed the above with the natural numbers from 0 up, and stack the
results in a pyramid, you get:

                           1       n = 0
                          1 1          1
                         1 2 1         2
                        1 3 3 1        3
                       1 4 6 4 1       4

That's Pascal's Triangle, or at least five rows of it. For years
mathematicians have been working away with it, finding all kinds of
interesting relationships between rows and columns and diagonals and so
on. You must have figured out by now that I'm leading up to something.


3.6 Pascal Meets Sierpinksi
---------------------------

If you substitute a black dot for all the odd numbers in Pascal's
Triangle, and a white dot for the even numbers, you get a triangle that
begins to look much like the Sierpinski Gasket. If you're using enough
rows, it looks *exactly* like it.

In the program below, I've used the above BNOM2 to generate the Pascal
binomial coefficients, and the GASK structure to plot them in a pyramid.
Each row/column position gets one coefficient, which is checked to see
if it's odd or even. If it's odd, that pixel is turned on. If it's even,
that pixel is skipped.


Program: PASC  The Gasket from binomial coefficients  Execution time: 2.2 min.

%%HP: T(3)A(D)F(.);
\<< ERASE { # 0d # 0d      @ Set up graphics display.
} PVIEW 0 63               @ Start Y (vertical) loop.
  FOR Y 0 Y                @ Start X (horizontal) loop.
    FOR X
      IF 'COMB(Y,X)        @ Find the binomial coefficient for Y,X
' EVAL 2 MOD 0 \=/         @ and test it for odd/even.
      THEN X 65 + Y        @ If odd, turn on that pixel.
2 / - R\->B Y R\->B 2
\->LIST PIXON
      END
    NEXT                   @ Step to the next position.
  NEXT { } PVIEW           @ Press ON to exit graphics screen.
\>>

  Stack:
  No input required


The first two-thirds of the display looks identical to the output of the
Sierpinski program. But then as it continues, it begins to look as if
we've blown a Gasket. There's nothing *seriously* wrong, but the
triangles appear to be starting too soon, throwing the pattern off.

If you exit and press Picture, you can use the (x,y) key and the arrow
keys to cursor to the problem area and find the row value (you'll have
to use Enter to put the coords on the stack, and then
PRG-PICT-NXT-C->PX). It seems to be happening at row 43. Put 43 on the
stack and run BNOM2 to generate the list of coefficients. Looks okay so
far.
    But press View and cursor down to see the middle part of the list. The
coefficients are getting bigger and bigger, and the sudden appearance of
exponential notation says that the Dreaded Roundoff has occurred.

There are ways out of this; the combinatorial function could be broken
into smaller parts to keep down the size of the factorials it uses, or
replaced with methods that don't use factorials at all, but the real
problem is the ever-growing coefficients themselves. It should be
possible to derive the odd/even relationship without even generating the
coefficients - and there's another project for you.

And that's all I have room for, as we come full-circle back to the part
about precision in iterations. I hope that you've enjoyed this one-tenth
as much as I've enjoyed researching and writing it. There's so much I
didn't cover - but then if there's enough interest in this, I'll have
lots of material for a sequel.

  Special thanks to Peter Karp for reading the draft version and
  offering suggestions, and to the members of comp.sys.hp48, always
  there with help for programming problems.

  This article is available for downloading in plain text from the HP48
  archives at: http://www.hpcalc.org/docs/misc/


Regards,
Bill Markwick,
Toronto, Ontario, Canada
bd628@torfree.net


REFERENCES
----------

The first book in the list is probably the premier book on chaos/fractal
theory; at nearly 1,000 pages, it probably costs a million, and if so,
it's worth every penny. Al Shenk's book has nothing on chaos theory, but
has a wonderfully lucid explanation of iterative functions (and
calculus); it's the one that inspired my curiousity about the subject in
the first place.
  I also highly recommend Michael McGuire's book; he's a physicist who's
also a great photographer, so you get both technical and artistic points
of view.


  Chaos and Fractals - New Frontiers of Science, Heinz-Otto Peitgen,
  Hartmut Jurgens, Dietmar Saupe, Springer Publishing, 1992.

  The Beauty of Fractals, Heinz-Otto Peitgen, P.H. Richter,
  Springer-Verlag, 1986.

  Encounters With Chaos, Denny Gulick, McGraw-Hill, Inc., 1992.

  The Nature and Beauty of Mathematics, Donald Davis, Princeton U.P.,
  1993.

  Calculus and Analytic Geometry, Al Shenk, Scott, Foresman and Co., 1988.

  Fractals, Hans Lauwerier, Princeton U.P., 1991.

  An Eye for Fractals, Michael McGuire, Addison-Wesley Publishing, 1991.

    See also: Usenet's sci.fractals, and its FAQ at
              http://fractal.mta.ca/sci.fractals-faq/

                               ---//---

