Chaotic Fractals

 "Gravity  can  not  be held responsible for  people  falling  in
love."
                                                  Albert Einstein

      CHAOS THEORY, FRACTALS AND THE UNATTACHED PROGRAMMER
                   an Introduction by Ringpull

 Chaos theory,  eh?   What's it all about then?   In this article
(and  possibly  others)  I hope to explain  and  experiment  with
strange  and  currently fashionable  branch  of  mathematics.   A
spin-off here is that it also gives me somewhere to vent my views
on the world now that Pervert's Monthly is no more,  so there may
be numerous detours on the way!

 OK,  Chaos theory:  What is it,  Why is it and Where is it.  The
simplest  description  of a chaotic system is one where  a  minor
variation  on the input produces a huge variation in the  output.
The  classic  example of this is the famous  'butterfly  effect',
where the beating of a butterfly's wings in South America  causes
a  hurricane over Europe six months later.   This is because  the
atmosphere  is  a very complex and dynamic system which  is  very
sensitive to its initial conditions.
 Imagine  you had two identical planet Earths.   On one of  these
Earths a butterfly flaps it's wings creating a minor airflow  and
on the other Earth it doesn't.   As time goes on,  this minor air
turbulence starts to show differences between the two Earths.  At
first these are very small but the further into the future we go,
the  greater the difference until six months later when  it  gets
very  windy  and a lot of people have a very  miserable  holiday.
This  has resulted in a strong case for the extermination of  all
South American butterflies.
 My  own variation on this theory is that an accident on the  M25
this  morning  resulted in me meeting another car  while  driving
along  a narrow street in a small town in nothern  Scotland  this
afternoon.   Failing  to give way to this vehicle resulted in  me
failing my driving test and feeling quite miffed at having wasted
£26 on the test fee.
 If  you have seen (or read) "Jurrasic Park" you may  recall  the
mathematician (played by Jeff Goldblum) who keeps saying that the
dinosaurs will inevitably escape because of chaos  theory.   This
is   somewhat misleading as it is not chaos theory but  the  much
more  common Murphy's Law (What can go wrong will go wrong).   It
would   appear that Crichton could have done some more  research,
but   fortunately  he  is  now concentrating  on  the  much  more
worthwhile   task  of  upsetting women with his  new  book  about
sexual harassment.

 The  reason  that chaotic systems are predicable  in  the  short
term  but become more unpredictable as time goes on is that  they
are  dynamic.   This means that the output is fed back  into  the
system  as  the  input.   For example;  today's  weather  is  the
starting  point for tomorrow's weather so if today's weather were
different   then obviously tomorrow's weather would be  different
too.
 Chaotic systems aren't just limited to abstract things like  the
weather  but  can also be represented as  mathematical  formulae.
As soon as something becomes mathematical we can turn it in to  a
bunch  of  instructions  and shove it into  our  computer  to  be
mangled  at our own will, and this is where the fun begins.

 What  does  a graph of a chaotic system  look  like?   You  have
probably seen one in the form of the famous Mandelbrot set.  This
is in fact a graph of the function z = z² + c  where z and c  are
complex numbers.   Eh?   All numbers are complex to me if I don't
have a calculator!
 A  complex  number  has two parts to it;  a  real  part  and  an
imaginary part.  Each of these parts can have any value, giving a
number of the form z = x + yi (where i = ?-1).
 We  plot a Mandelbrot set by picking a point on the  screen  and
putting  the  x and y coordinates into the x and y values  of  c.
Both  parts  of  z start as zero and we keep on  squaring  z  and
adding   c.   One of two things will happen as we  continue  this
process.    The  value of z will either level off or continue  on
until   infinity.   If z levels off then it is said to be in  the
set,  if  it  shoots off to infinity then it is outside the  set.
On your  typical picture of the Mandelbrot set  the black area in
the   middle  is where z levels off and the  coloured  parts  are
where it  doesn't.  The coloured bands often found on such images
depend  on   the  number of iterations of the  formula  it  takes
before the  routine decides that z is not going to level off.   A
true  Mandlebrot set is monochrome and hence rather boring.

 If  we  take  our z = z + c formula and rewrite  it  a  slightly
easier to deal with form, we get:
   x = x² - y² + cx
   y = 2xy + cy
here cx and cy are the coordinates of the pixel.  Starting with x
and  y  both equal to zero and assuming that the  equations  will
continue to infinity if x²+y² rises above four,  we can construct
the following routine to calculate the color of a pixel:

mandel(x,y)   // Routine to find color of point x,y
    z_x = 0   // Start at zero
    z_y = 0
    count = 0 // Start the loop counter at zero
    REPEAT
         temp_x = x*x + y*y + x // The new x value
         z_y = 2*x*y + y                // The new y value
         z_x = temp_x
         count = count + 1              // Increase the counter
         IF (x*x + y*y) > 4             // Is z going to infinity
              COLOUR count MOD 16       // Give pixel a color
 depending
              PLOT x,y                  // on the value of the
 counter
              RETURN                    // And that's it
         ENDIF
    UNTIL count > 100   // Number of iterations to try
    COLOUR 0            // Pixel is in the black lake
    PLOT x,y            // Plot it RETURN

 As you can see, it is simply a case of continuing the  operation
until z exceeds the trigger value.   When it does,  we  assume it
is outside the set and the point is given a colour  according  to
the  number of iterations it took to exceed the   trigger  value.
This gives the set its characteristic colour  bands.   If z  does
not  exceed the trigger value within a set number  of  iterations
(in  this case 100) then we assume that the point is  inside  the
lake and we colour it black.
 By  using a couple of simple loops you can use this  routine  to
plot  a Mandlebrot set on your screen.   One important  point  to
remember is that the set lies within the area between -2 and 2 on
both the x and y axis,  hence some form of scaling is going to be
required  to  convert  screen  coordinates  into  Mandlebrot  set
coordinates.   It is also necessary to use real variables  rather
than integers for the x and y values.
 Once  you  have written a program to plot the set you  can  have
all sorts of fun by experimenting with different colour  palettes
and some psychedelic colour-cycling!   You can also try  changing
the formulae to get different fractals, for instance try cubing x
and y rather than squaring them.
 The chances are that your Mandlebrot set plotter will be  slower
than  some  of the other programs you may  have  seen.   This  is
because  there are a number of tricks which can be  exploited  to
speed  up  the process.   One is using the fact that the  set  is
symmetrical and mirroring it in the x-axis.   Periodicy  checking
can speed up calculation of points within the set as the value of
z  tends  to cycle.   Detecting this cycling means we  can  avoid
having to calculate all 100 (or whatever)  iterations.   Guessing
routines  can speed up calculation of the large areas  of  colour
outside the set.
 Currently   the   most  fashionable  trick  to  speed   up   the
calculations  is to use integer math rather than  floating  point
routines,  which  are rather slow if you don't have a maths   co-
processor (And the ST doesn't).
 All these tricks are employed by the more sophisticated  fractal
programs,  such as Fractint on the PC.  If you have a PC  (Yeuck!
Blugh!) you might want to get hold of this program as it  is  the
most comprehensive fractal plotter around.
 When  I  get  around  to  adding a  user  interface  to  my  own
assembler  integer  Mandlebrot plotter I will let you see  it  in
another  instalment of this column.   At the moment you  have  to
enter the coordinates in the source code and re-assemble it.

 Next  time we will have a look at fractal landscapes and how  to
build these miniature virtual realities on your ST!   I leave you
with  a little song for which I must thank Jack Schofield at  the
Guardian for bringing it to my attention.

Sing to the tune of the Beatles' Let It Be.

"When I find my code in tons of trouble,
 Friends and colleagues come to me,
 Speaking words of wisdom: ''Write in C.''

 As the deadline fast approaches,
 And bugs are all that I can see,
 Somewhere, someone whispers:
 ''Write in C.''

 Write in C, write in C,
 Write in C, oh, write in C.
 Lisp is dead and buried,
 Write in C.

 I used to write a lot of Fortran,
 For science it worked flawlessly.
 Try using it for graphics!
 Write in C.

 If you've just spent nearly 30 hours
 Debugging some assembly,
 Soon you will be glad to Write in C.

 Write in C, write in C,
 Write in C, yeah, write in C.
 Only wimps use Basic.
 Write in C."

 See you Later!