  ________________________________________________________________________
 /                                                                        \
|                     ARCHIMEDES FRACTAL GROUP Newsletter                  |
|                              November 1991                               |
|                            from Mike Curnow                              |
 \________________________________________________________________________/ 


Introduction
============
A big hello to you all and thanks to all of you who have written to me for
programs, help and contacts. AFG has achieved coverage in the press and is
becoming known as the source for fractal knowledge on the Archimedes.

When I started this venture back in May I did not know quite what to expect,
and was happy just to hear from anybody into fractals on the Archie. Now
that I have had numerous replies from all over the country and from abroad,
I am still confused what to do with AFG since everybody approaches things
from different angles. The aim of this newsletter is to keep you up to date,
pass on some knowledge I have gained in the last 6 months whilst writing
!Fractal (my major fractal pre-occupation), and to let you know what I plan
for AFG in 1992.

Contacts
--------
For people into writing their own programs and experimenting with others,
there soon comes a point where the books and publications leave you
stranded. This is often made worse by people who feel afraid to pass on
their techniques, jealously guarding them as their own or not knowing that
it is very frustrating to show a fractal without explaining how it can be
recreated.

I subscribe to the Stone Soup philosophy advocated by the authors of
Fractint - if you combine the small offerings of many people you end up with
a feast for all. So when frustration has beaten you down, set pen to paper,
and try introducing yourselves to one of these people who I hope will be
glad to offer help. If your name is not on this list, please let me know
stating your area of interest (if any). Of course I am always willing to
help too.

Joyce Haslam, 112 Keighley Road, Colne, Lancs. BB8 0PH
                                   
John Greening, 15 Pentland Crescent, Edinburgh, EH10 6NS

John Hedley, 133 Russell Drive, Wollaton, Nottingham, NG8 2BD

Jean Mourik, BOX 983, 3300 AZ Dordrecht, Netherlands

Ian Nicholls, 67 Habberley Road, Kidderminster, Worcs, DY11 5PN

James Vernon, 20 Grove Hill, Topsham, Devon, EX3 0EG 

These people have all contributed material to AFG so I presume they can
help. Joyce in particular loves to write and has contacts with the PC world,
such as Larry Cobb (c/o Bay House, Dean Down Drove, Littleton, Winchester,
Hants SO22 6PP). (Not quite sure why the J's proliferate).

AFG Software Disks
------------------
After the publicity in Micro User I was deluged with disk requests, with the
result that fractal work took a back seat for a while. To cater for those of
you who just want the programs, I have rearranged the collection sorting out
the PD from that which definitely wasn't. The original disks have been
compressed onto 1 by excluding images and using !Spark. It contains programs
sent to me over the past few months which the authors have said are Public
Domain. I have called the disk AFG_1991 (sorry about the lack of
imagination), and it has been sent to these PD libraries who will become the
prime source:

APDL, 96 Lanehouse Road, Thornaby, Cleveland, TS17 8EA
Diamond PD, 86 Meadowbank, Moor Lane, Holyway, Holywell, Clywd CH8 7EF
DataStream, 32 Hollinwell Avenue, Nottingham, NG8 1JZ
Skyfall, PO Box 2220, Birmingham, B43 5RZ

So please write to them to get copies, mentioning the AFG collection.
However I will not turn away requests for disks - I just want to reduce my
workload. A contents list is provided at the end of this article.

--------------------------------------------------------------------------

Speed
=====
One of the most frustrating aspects of fractal programming is the amount of
time the images take to produce. The following hints and tips address some
of the issues and solutions I have encountered whilst programming over the
last few months.

Hardware
--------
The easiest way to speed things up is to upgrade the hardware, and for the
Archie that means buying an ARM-3 processor. This upgrade is now available
for the A3000 and has been slashed in price to 230 (it was double that).
The ARM-2 runs at 8Mhz, giving a maximum of 8 million instructions per
second (mips), whilst the ARM-3 runs at 25 to 30 Mhz, ie 25-30mips (the
manufacturers cannot guarantee that they will run at 30Mhz). This will
produce a speed increase of 2-5 times, depending on the code.

The speed increase varies depending on the amount of memory access -
instructions which access memory see little speed increase since the main
memory speed remains the same at 4Mhz. To overcome this vast difference in
speed the ARM-3 uses a 4Kb cache for instructions (not data). Since fractal
programming involves a lot of numeric processing rather than data movement,
5 times speed ups are often achieved. !Fractal has been specially written
with this in mind.

Floating point arithmetic is notoriously slow because it is normally
emulated in software. To overcome this a floating point processor is
required - this will execute the main floating point instructions directly
and will perform better than an ARM-3 upgrade. Currently the FPU and ARM-3
cannot be run together, though I believe Acorn are due to release a
compatible FPU. The major drawback is cost - the FPU is very expensive for
the Archie, about 600.

To use the floating point instruction set you need to program in a language
other than BASIC V which does not use the FPU. I do however possess a copy
of BASIC VI which uses the FPU if you are interested.

An alternative to an ARM-3 upgrade is the A5000 which comes with an ARM-3
and faster memory. At 1500 it is the best value Acorn machine and brings
the Archie back on par with recent PC developments. If you have an A3000,
the A5000 offers a good upgrade path with its 40Mb disk, 2Mb of memory and
multiscan monitor.

Owners of multiscan and VGA monitors should note that the there is a price
to pay for the extra resolution. Due to the shared use of memory by vdu and
processor, using higher resolution displays reduces processing speed due to
the need to allow more access to the memory by the VIDC chip. PCs overcome
this problem by using separate memory for vdu and programs. Watford have
just produced a graphics add on board which does the same for the Archie, so
this may be a good buy if you want to have your cake and eat it.

Software
--------
If brute force doesn't solve the problem, try a little intelligence. There
are many ways a program can be speeded up, such as:

a) use a different programming language.
b) re-write the core routines more efficiently.
c) find a better algorithm.
d) use approximations rather than absolute values - sometimes a trade off in
quality can dramatically increase speed. 
e) pre-calculate values, eg. using SINE and COSINE tables.

If you rate the three main programming languages for the Archie by speed you
get:
   BASIC (uncompiled)
   C
   Assembler
though when comparing the FPE instruction set versus BASIC floating point
variables there is little difference in speed.

Using the iceberg principle, 10-20% of most programs tend to do the most
work, and this is especially true of fractals which are very iterative. So
convert that to assembler, and leave the rest. The Mandelbrot equation can
be written in Assembler with surprisingly little code.

Integer versus Fixed Point versus Floating Point
------------------------------------------------
Computers can add, subtract and shift binary numbers. Any other arithmetic
requires multiples of these core functions and therefore take longer.
Integer arithmetic is the quickest but is very restrictive in its number
ranges. Most fractal equations require floating point which offers a much
large range of numbers and more accuracy - up to 19 digits on the Archie.

A halfway house is to use fixed point arithmetic, that is numbers with a
fixed number of decimal (or binary) points. These can be computed with the
integer instruction set and thus offer a speed advantage over floating
point, but suffer from a very small range of numbers. Happily for
Mandelbrots and many 3d transformations this limited range of numbers is
often sufficient for most processing.

Fixed point using binary is a little difficult to understand at first, but
works just the same as fixed point decimal. If we have a 16 bit binary
number we could assign 8 bits to the integer range, allowing numbers from
-128 to 127, and 8 bits to the binary places. Written in binary, the various
bits have the following values :

   bit:   15 14 13 12 11 10  9  8 .  7   6   5   4    3    1    0
 value: sign 64 32 16  8  4  2  1   1/2 1/4 1/8 1/16 1/32 1/64 1/128

Thus 10.25 would be %00001010.01000000 or x0A40.

Adding and subtracting can be done using the standard ARM ADD and SUB
instructions. When you multiply a fixed point number by another, you end up
with double the number of fractional places eg. 10.25*10.25=105.0625. With
our 16bit fixed point number we thus end up with 16-bits of integer and
16-bits of fractional places, and so the number can be "normalised" by
simply shifting it 8 bits to the right.

When using the full 32 bits of the ARM registers you end up with a 64 bit
result. To get this using the ARM's 32-bit registers requires 4 multiplies
and a few adds! Why? Well take 2 registers, split each into 16 bits to avoid
overflow (16bit*16bits=32bits) as follows:

   R0*R1 -> ab*cd = +     b*d     where abcd are 16 bits of a register
                    +   a*d
                    +   b*c
                    + a*c

Evenso, the result is still much faster than floating point, and this
technique is commonly used, especially in graphics programming. Note that
multiplying a fixed point number by an integer leaves the binary place
unchanged, and thus only needs one multiply, which is very suitable for SIN
and COS adjustment.

As you may have gathered from the foregoing discussion, fixed point is the
preserve of Assembler because of the need to detect for carry and for
special treatment of negative numbers. Supplied with !Fractal is a set of
Assembler macro functions that can be used to handle the necessary 32 bit
fixed point arithmetic, including a divide routine.

32 Bit Floating Point
---------------------
Fixed point arithmetic has a limited range of numbers which makes it
unsuitable for Newtonian approximation routines for example. To overcome
this requires creating a set of true floating point sub-routines. If you
have the application !Mandy you will find a lot of the necessary code,
although mostly undocumented. Ian Nicholls points out that a lot of the
necessary maths and programming is also in the Fractint source, though
written for 80386 assembler.

Recently I have had go myself and have produced the routines for add,
subtract, multiply and divide. I stuck to the Acorn 32 bit float format for
compatibility, and early results suggest a speed improvement of 2-5 times.
This was not as much as I expected, but better than nothing. It seems a lot
of the FPE overhead is due to the entry & exit code, and converting numbers
to and from the float format to perform the arithmetic. Thus the speed
increase you gain is mainly through reduction in the entry and exit code.

If anybody is interested in developing this code further, please contact me.
It is my intention to incorporate it into !Fractal where appropriate.

Mandelbrot Speed Ups
--------------------
In writing !Fractal I incorporated two common speed up techniques. The first
is to use a multi-pass plot, where we first do a rough plot and then fill in
the gaps. On subsequent passes, if all four points surrounding a pixel have
the same value (colour), then we assume this pixel will also be the same,
otherwise we calculate its value. We start off with a 4x4 grid and use 5
passes to construct the grid. Not only does this produce up to 80% speed
increase, it also allows you to see the full image at an early stage. This
technique works best when there is not too much detail on the image. My
thanks to D. Stevenson in Fractal Report No.6 for this routine.

The second technique is to detect when we are in the interior of the
Mandelbrot, when even an infinite number of iterations will never give a
result. When generating the Mandelbrot an escape value is calculated thus :
u*u+v*v<limit, where limit is usually 4 but may be any value. For values of
x & y inside the Mandelbrot, u*u+v*v will quickly settle to 0 or some other
value, long before we reach the maximum iteration count. Thus we need to
simply remember the result of this calculation and compare it with the next
- if they are the same then we bail out. This is known as periodicity
checking and is most effective when using iteration values >128.

There are other techniques available. John Greening has supplied a routine
which maps the contour lines of the Mandelbrot in a few seconds (even using
OS_Plot - I was amazed).

ARM Instruction Speeds
----------------------
Keen Assembler programmers will know that the ARM does not execute all
instructions at the same rate. As already mentioned, multiplies will take
longer since it is made up of shifts and adds, whilst memory referencing
instructions are slowed by the speed of memory in use, most notable with the
ARM-3 chip. To satisfy my own curiosity I came up with the following results
based on a simple timer loop.

With an ARM-3 you get about 30 million instructions per second, and 7.5
million per second on an ARM-2 (not including interrupts), ie. 1 instruction
per cycle.

Adding conditions or fixed SHIFTs doesn't affect speed. A register SHIFT
takes 2 cycles. eg. ADD R1,R2,R3,LSL R4

A STR is just as fast as a STRB, but obviously has the advantage of storing
4 bytes at once. A STM is just as fast as STR for 1 register and in general
a STM is 2-3 times quicker than a sequence of STRs. So use STMs to save
multiple registers where possible. A STR on an ARM-3 takes just as long as
an ARM-2 due to the memory slowdown. Writeback doesn't affect speed.

A MUL is 17 times as slow as an ADD. MLA takes the same time.

A branch takes 3 cycles. BL is just as quick.

So you can see that even with the ARM's limited instruction set, choosing
the instructions carefully can produce significant speed ups. This is very
noticeable in loops which reference every screen pixel - there are 327,680
of these on a mode 21 screen. In particular it is interesting to note that
the fixed shifts don't affect processing speed. Consider for an example a
routine that converts an x/y pixel value into a screen address. We could
write:

       MOV R0,#640             ; width of 1 screen row
       MUL addr,y,R0           ; row offset
       ADD addr,addr,x         ; column offset
       ADD addr,addr,base      ; screen address

which takes 20 cycles. Using the shift facility we can get:

       MOV addr,y,LSL #10      ; multiply y by 512
       ADD addr,addr,y,LSL #8  ; add on y*128, ie. y*640 
       ADD addr,addr,x         ; column offset
       ADD addr,addr,base      ; screen address

which only takes 4 cycles, 5 times faster! The shifts allow us to perform
multiplications of fixed amounts much fast than the MUL instruction. Also
don't forget the MLA instruction - we could have written MLA addr,y,R0,x in
the first example to save 1 instruction. Shifts also work very fast in C and
BASIC.

Direct Screen Writes Versus Plotting
------------------------------------
On the BBC-B using direct screen writes was de-rigeur to get sensible
graphics speeds, and the same applies to the Archimedes due to the increased
screen resolution. If you try plotting every screen pixel you will see what
I mean. RiscOS is a great help by supplying all the information we need
about the screen mode, such as its start address, row width, OS unit to
pixel conversion factors and so on. It is best to stick to 256 colour modes
where 1 byte equals 1 pixel. Remember also that you can just as easily write
directly to a sprite, and then send that to the screen - this is necessary
when writing desktop programs.

This is fine for pixel drawing, but what about drawing lines? This is a
little trickier but a visit to my local library uncovered a suitable routine
in a book on graphics programming (Applied Concepts In Microcomputer
Graphics - B.A.Artwick, Prentice Hall). There are stepping techniques that
produce smooth lines at any angle, using only add and subtract instructions
as we go. This is known as the digital differential analyzer (DDA) and comes
in quadrantal and octantal forms. The same book also covers many other
useful speed ups and graphics approximation techniques such as circle
drawing, SIN and COS approximation and so on.

--------------------------------------------------------------------------

Fractal Ideas
-------------
If, like me, you have run through the basic Mandelbrots, Julia Sets, Henon
and Lorenz attractors, L-systems, Iterated Function Systems and Midpoint
displacement techniques (as used in landscape generators), you are probably
wondering what comes next. My answer to that is to look again and put your
imagination to work.

Take the Mandelbrot set for starters. The well known equation uses f(z*z+c)
as its basis, but there are many other functions that work. In !Fractal I
have 6 types so far, but I know there are many more and would be interested
to hear from anybody who has come across others in journals and so on. Joyce
Haslam for example came up with the Popcorn by Clifford Pickover which is
based on SIN and TAN and gives very different results.

There is a lot of scope in L-systems for generating very realistic images.
John Greening has sent in 45 examples written using a very simple BASIC
program. Some of these take the standard turtle commands and add others for
colour, line thickness and image fill in, and the results are startling. The
next step would be to add small sprites for parts such as leaves, flowers,
background and so on. In fact these sprites could very well be generated
using the L-system rules. Thus you could develop an L-system construction
set to produce your own fractal forest and garden. Add a little randomness
to the generation procedure and you could end up with an infinite variety of
fractal plants.

If you look at the book the Algorithmic Beauty of Plants you will find a
description of the commands necessary to add 3d commands for even greater
realism. I believe this could all be accomplished in a BASIC program at a
reasonable speed and without undue complexity. The L-system also lends
itself to implementation using the RiscOS draw module commands because it is
basically made up of small lines. Thus rather than generate sprites,
generate a draw image for greater control, resolution and post generation
manipulation. L-systems exist within !Fractal and I am tempted to add some
of these features at a later date.

The IFS technique has received little attention. I believe this must be
partly due to the complexity of deriving the IFS weightings necessary to
draw an image. Whilst L-systems are conceptually easy to visualise, I have
yet to see a method for deriving IFS codes, though I have to admit at not
reading any of Michael Barnsley's writings on this matter (in !Fractal I
just cribbed Fractint!). However I am aware that a lot of research has been
done at using IFS to produce image compression, in fact I believe commercial
software is due to become available. Does anybody have anything to add on
this subject?

I have had a lot of fun playing with 3d transformations of fractal shapes -
in !Fractal there are currently 4 ways of manipulating the resulting fractal
image. Currently I transform the image after generation. However it appears
to be a very simple matter to generate the 3d shape at fractal generation
time for those functions that map each pixel. To do this, rather than take a
2d image and transform it to 3d, we work in reverse. That is we take each
pixel in the end image, work out the x/y pixel co-ordinate of the source,
and then generate the fractal value of that point.

Using this idea would allow you to write a program that offered 3d zooming
and panning around a Mandelbrot for example, or maybe around a landscape.
John Greening sent in a basic 3d Mandelbrot program (on the AFG_1991 disk)
which may be a place to start. The Gwawpscape program in August's Acorn User
is also a good example and maybe a starting point for inspiration.

When transforming sprites into 3d via rotation and globe mapping I found it
was necessary to use this inverse mapping technique. Normally graphics
shapes are transformed by taking the x/y (and possible z) co-ordinates, and
then apply SIN & COS factors as required. For example to rotate, new
x=x*COS(angle)-y*SIN(angle), and new y=x*SIN(angle)+y*COS(angle). This works
fine for points on a line which are then drawn in, but with pixel values you
end up with some source pixels mapping onto the same target pixel, leaving
others blank. To overcome this I worked in reverse which meant that some
source pixels mapped into multiple target pixels leading to some fuzziness,
but at least all the target pixels get filled.

As stated earlier most 3d transforms can be performed using fixed point
assembler which allows high speed manipulated of pixel points, but BASIC
integers could be used in many circumstances. I am sure fascinating images
could be generated by taking the standard fractal shapes and mapping them
onto other shapes.

Another area waiting to be explored is animated fractals. One idea is to
produce a constantly zooming Mandelbrot - John Hedley has done some
exploration in this area. Let's hope he succeeds. Alternatively you could
regenerate the image continuously varying one of the parameters by small
amounts. Julia sets would be a good basis, since small adjustments to c-Real
and c-Imaginary gradually alter the shape, or why not try Melting
mandelbrots (see Fractal Report no.2). Using Mode-13 and a smallish shape,
several frames a second could be achieved.

A common technique to cheat at animation is to pre-generate the images and
re-play them as a film. To get any length requires a lot of images, but
interpolation can be used to guess the intervening frames. This works in a
similar way to the solids guessing technique used in Mandelbrot generation.
The book Science of Fractal images discusses some of the issues involved in
this area, such as how to minimise the errors in pixel guessing. Using such
a technique could allow maybe 10 frames to be displayed for each one
generated, allowing quite long movies to be made.

An area I intend to explore and develop is landscape generation. There are
several methods available, some of which lend themselves to implementation
in Assembler. The idea of a landscape that can be travelled around by the
mouse, a-la virtual reality, is appealing. Also it would be possible to add
L-system plants and trees, brownian motion clouds (as featured in Science of
Fractals), and maybe fractal rivers!

I have done very little on collating the various cellular automata programs
other than the ones sent in to me. Many have appeared in Acorn User and I
hope to type them in one day, along with the various BBC & Archimedes
programs from Fractal Report. I am sure that a lot more could be done by
using a combination of cellular automata rules on fractal shapes and vice
versa.

All in all there looks as if there is lots that can be done, it just needs
some imagination, quite a bit of time and a lot of patience! Happy fractal
hunting.

--------------------------------------------------------------------------

Spreadsheets For Fractal Exploration
------------------------------------
I forgive you for thinking that spreadsheets and fractals don't mix, but if
you are puzzled as to how fractal equation performs they can be very useful.
I was turned on to the idea by the book Dynamical Systems And Fractals by
Becker and Dorfler, and have found it particularly useful to watch the way
the numeric series progresses. It has also proved invaluable as a diagnostic
tool.

Any spreadsheet can be used, including the many shareware packages that run
under the PC emulator. Intersheet is available for the Archimedes for about
25. For an algorithm such as the Mandelbrot, the method is to lay out the
various steps of the routine across the columns, starting say in row 3 or 4.
The first few rows should be left for entering variables such as the initial
x and y values, bailout limit and so on.

On the first row of the formula the initial values are plugged into the
equation. Copy this row to the next and alter it to pick up the new values
of x/y/u/v etc as required. The formula can then be replicated down the
remaining rows as many times as required - about 50 is sufficient for a
Mandelbrot. Now you can enter the values of x/y etc and see the numeric
progression. For Mandelbrot's the periodicity that results for interior
values is readily seen - in fact this is how I stumbled upon it.

Many of the better spreadsheets have built in graphing facilities which can
be put to use. This is particularly useful when examining bifurcation
diagrams and strange attractors. Note that we can do all of this without
writing a single line of code. Also spreadsheets don't crash when numbers
get too large are small, so it is possible to detect when numbers get out of
range. This is particularly useful for determining if a routine can be
implemented using fixed point arithmetic.

--------------------------------------------------------------------------
1992 And All That
-----------------
It is my intention to make !Fractal available shortly via Archimedes World
seeing as they are the only magazine that feature on the cover disks, and
the editor has a soft spot for fractal programs. Some of you have already
seen !Fractal in one or more guises, but it is still being expanded, and
will carry on doing so even after publication. I have recently added the
facility to import any 256-colour sprite so that the built in 3d routines
may be used. Hopefully !Fractal will stir more interest so that the AFG
membership will grow and and thus more programs and ideas will result.

Hopefully John Hedley will release his real time Mandelbrot program
sometime. Ian Nicholls sent me a smart looking application called !Chaos
which he says should be appearing soon (how is it going Ian?). John Greening
has recently sent me a whole batch of fractal programs so I imagine he has a
lot more to come from his "Fractal Factory". 

Joyce Haslam is delving into the world of Fractint and coming up with
delightfully simple versions in BASIC which I have been struggling to get
into !Fractal.

--------------------------------------------------------------------------
Mike Curnow, November 1991
30 Bowen Drive,
West Dulwich,
London
SE21 8PN
                       
                   <<<< MAY CHAOS BE WITH YOU! >>>>
