Recursion 2018

Perhaps this?

Hmm… I’m sure I must have seen that at some point, but if I have I’ve forgotten. I’ll try to find some time to run it tomorrow to see it running for myself.

However, I think even reducing PROCpoly would still result in something unwieldy, given that I want to put it on a four page A5 pamphlet, with accompanying text! :)

Maybe you can have a challenge to see who can beat me to adding trees and cars (so far, two years and counting)

It might be too big for my little pamphlet, but it might be worth having it on one of the MUG machines as part of the code club idea of Doug’s, with some print outs of the program, and giving people a little challenge along those lines.

People like visual stuff. Remember the days when you’d pick up an AU at WHSmith and the first thing you’d do is flick to the *info column, or just the yellow pages, to see if there was a creation of Jan Vibe’s to type in? Or was that just me?

No, that wasn’t just you. :)

But that does remind me – just after the last Recursion, I discussed with Richard Ashbury that it would have been a nice idea to have some of his modified Jan Vibe programs running as a rolling demo on a spare machine if there was room to set one up. Something else to consider for this time around. (Though my one table didn’t really leave much room for that.)

it might be worth having it on one of the MUG machines as part of the code club idea of Doug’s, with some print outs of the program, and giving people a little challenge along those lines.

Already captured and yes we could have printouts on the stand and perhaps even stretch to a Pi Zero with RISC OS included as a prize. I’ll discuss this with the MUG team.

How about 23 lines of BBC BASIC that render the Mandelbrot set? (Well, to be more accurate, lots of points that aren’t in the Mandelborot set, colour coded by their degree of separation from it.)

This displays nicely in the centre of my 1920×1080 monitor via my Pi3 in about a minute but I’m no expert on MODE so I’m not sure if it’ll translate well to other environments.

Even if it’s no use for Recursion 2018, I found it an educational way to explore my new BBC BASIC manual, so thanks for the excuse!

MODE "X1280 Y1024 C256"
width% = 2000 : height% = 1200 : max% = 32 : row% = 0
WHILE row% < height%
  col% = 0
  WHILE col% < width%
    c_re = (col% - width%/2.0)*4.0/width%
    c_im = (row% - height%/2.0)*4.0/width%
    x = 0 : y = 0
    iterations% = 0
    WHILE x*x + y*y <= 4 AND iterations% < max%
      x_new = x*x - y*y + c_re
      y = 2*x*y + c_im
      x = x_new
      iterations% += 1
    ENDWHILE
    IF iterations% < max% THEN
      GCOL iterations% * 4
      POINT 300+col%,450+row%
    ENDIF
    col% += 1
  ENDWHILE
  row% += 1
ENDWHILE

EDIT: I should be clear that I just hacked one of the many implementations of this; I’m no mathematician! Specifically this one: Let’s draw the Mandelbrot set

EDIT: For my own education, I’d like to know a) How to plot the points faster in BASIC. b) How to centralise the image without the clunky offset. (VDU command?) Any pointers / observations would be appreciated by me.

a) How to plot the points faster in BASIC

There are a few easy optimisations you could make:

1. Replace the two outer WHILE loops with FOR loops
2. Simplify some of the maths. E.g. pre-calculate 4.0/width% and store it in a variable so that it won’t have to be recalculated (twice!) for each pixel.
3. An easy way to make it 4x faster is to realise that the coordinates used by VDU commands are at a different scale to the pixel resolution of the screen. There’s a bit of information about it on this wiki page (“Eigen factors”), and I think the BASIC manual will have an explanation as well, but to summarise, for most screen modes there will be 2 OS units per screen pixel. So by incrementing col% and row% by one for each loop iteration, you’ll be drawing to each screen pixel four times. Increasing the step to two will eliminate that and immediately make things faster.

Slightly more complex optimisations would be to avoid calling GCOL or POINT for every pixel. E.g. only use GCOL when the number of iterations changes, and use LINE to render horizontal strips instead of individual pixels. Or you can have a go at rewriting it to use array arithmetic (I have an array-based Mandlebrot renderer which I wrote as a performance test for BASICVFP)

b) How to centralise the image without the clunky offset. (VDU command?)

Yes, you can change the graphics window origin using VDU 29

Excellent. A range of optimisations I can get my baby BASIC teeth into. Thanks, Jeffrey!

There are a few easy optimisations you could make:

If you are doing the whole M set, which is symmetrical, you can double up by plotting the top and bottom at the same time. There are also other calculations to move to outside loops. However, the main user of time is the floating point complex number calculation.

Back in the early days of the Archimedes there was some competition to write the fasted M set plotter, both in BASIC and machine code. This generated many ‘tricks’ such as Jeffrey is suggesting.

I have an array-based Mandlebrot renderer which I wrote as a performance test for BASICVFP

Perhaps you are following in the steps of Sophie Wilson. ;-) During the development of ARM BASIC there was a keyword MANDEL which did the complex number calculation. There were vestiges of it in the source, but I do not have a recent version on hand to check.

In 2010, after the death of Benoit Mandelbrot, I wrote a MANDEL keyword into Basalt. However, that uses fractional integers, not floats.

Yes, you can change the graphics window origin using VDU 29

Or, indeed, ORIGIN. ;-) One graphic optimisation is to confine the plotting to only the significant parts of the set and its surrounds.

There are also other calculations to move to outside loops.

If this is to be a demo to young /novice programmers then would it not be a good idea to show the difference between non-optimal code and a set of optimising changes?
It then demonstrates that simply doing something that works is a bad idea and that something that is properly designed to work efficiently is a good idea.
Properly designed code can be much swifter, easier to follow and use less memory / disc space is the lesson.

All progress is achieved by making mistakes so hopefully my fumbling attempts with this program could serve as a guide.

I don’t want to hijack this thread but I will post a slightly optimised version of the above later. (Array arithmetic I’ll take away for a closer look…)

I do not have a recent version on hand to check [the keyword MANDEL ]

I have had a look, and it is not in v1.73, but it was in v1.29, appearing after OVERLAY.

I still think that seeing some simple BASIC render the Mandelbrot set can be an inspiring experience for kids so now that my code is less of a crime against efficiency, I’ll re-quote it:

MODE "X1280 Y1024 C256"
ORIGIN 300,450
width% = 2000 : height% = 1200 : max% = 32
half_width% = width%/2 : half_height% = height%/2
last_iterations% = 0
FOR row% = 0 TO height% STEP 2
  FOR col% = 0 TO width% STEP 2
    c_re = (col% - half_width%)*4.0 / width%
    c_im = (row% - half_height%)*4.0 / width%
    x = 0 : y = 0
    iterations% = 0
    WHILE x*x + y*y <= 4 AND iterations% < max%
      x_new = x*x - y*y + c_re
      y = 2*x*y + c_im
      x = x_new
      iterations% += 1
    ENDWHILE
    IF iterations% < max% THEN
      IF iterations% <> last_iterations% THEN
        GCOL iterations%*4
        last_iterations% = iterations%
      ENDIF
      POINT col%,row%
    ENDIF
  NEXT
NEXT

The massive saving was on compensatibg for the Eigen factor.

I’ve been watching this thread with interest!

As a programmer of just about the “Hello World” variety, I’m tempted to come to Recursion with a couple of Pi setups and some worksheets (like the above) for people to have a go on. Somewhere I have copies of the old Input magazine in digital format and could make worksheets from some of those listings for people to have a go at? A sort of “guess what it does” kind of thing.

I also have access to a Robot Arm that can be used with RISC OS, if I can get hold of the software .

It is just too tempting, sorry. ;-)

• The value of c_im only has to be calculated once per row.
• The value 4.0 / width% can be precalculated, which also avoids a division
• Adjusting the ORIGIN can eliminate the - half_width calculation
• The test iterations% < max% is duplicated.
• The WHILE iterations loop can be a FOR...NEXT loop.
• The values x*x and y*y are calculated twice.
• The intermediate value x_new is not necessary.
• NEXT should probably have a variable.

MODE "X1280 Y1024 C256"
width% = 2000 : height% = 1200 : max% = 32
half_width% = width%/2 : half_height% = height%/2
ORIGIN 300+half_width%,450+half_height%
scale = 4.0 / width%
last_iterations% = 0
FOR row% = -half_height% TO half_height% STEP 2
  c_im=row%*scale
  FOR col% = -half_width% TO half_width% STEP 2
    c_re=col%*scale
    x = 0 : y = 0
    FOR iterations%=0 TO max%
      X = x*x : Y = y*y
      IF X + Y <= 4 THEN
        y = 2*x*y + c_im
        x = X - Y + c_re
      ELSE
        IF iterations% <> last_iterations% THEN
          GCOL iterations%*4
          last_iterations% = iterations%
        ENDIF
        POINT col%,row%
        iterations%=max% :REM exit the FOR loop
      ENDIF
    NEXT iterations%
  NEXT col%
NEXT row%

Come on, Steve!

x = c_re : y = c_im
FOR iterations%=1 TO max%

No point testing if 0*0 + 0*0 <= 4 :-)

No need to be sorry, I’m learning!

I’ll try that out and I’m going to use this as an excuse to go on to learn some other skills and make it interactive… (err, off this thread.)

Come on, Steve!

Ah, yes, that is how I do it here, but you can have just too much cake at one time. ;-)

My next offering would be to chop off the right hand side of the plot with:

  FOR col% = -half_width% TO half_width%/4 STEP 2

Then there is the representation of complex numbers by matrices. ;-)

Put time%=TIME near the start and PRINT TIME-time% at the end and you’ll know how many centiseconds it took!

Currently 2242 here, Jeffrey’s last mod saving 38cs, an improvement of 1.67%!

Thanks everyone. Yes, I’m aware of TIME and had been using that to measure improvements. Matrices is my next step, so no spoilers on that front, please. :-)

I’m tempted to come to Recursion with a couple of Pi setups and some worksheets (like the above) for people to have a go on.

andym, MUG would love to have you attend Recursion with us and why not bring along your robot arm as well.

In the meantime thanks to everyone who has contributed to this thread and for the examples.