fast Mandelbrot fractal generator

Basic and Machine Language

Moderator: Moderators

Post Reply
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

fast Mandelbrot fractal generator

Post by Mike »

As a follow-up to the 'slight' topic deviation in the thread about 'New frontiers in VIC Hires, Part 5', here is:

MANDEL V2, a fast Mandelbrot fractal generator for the VIC-20 (+8K RAM expansion required, download here)

Image

The *.zip archive contains:
- a *.d64 with MINIGRAFIK, MANDEL V2, SLIDE SHOW, 1 image of the complete set, and all 10 fractal images from tokra's list.
- source code of the ML part,
- tokra's co-ordinate list, and
- versions of the pictures in 800x576, computed on a today's PC.

I translated the main loop of the calculations in line 17 of the original program into ML, getting an almost 3x speed-up with the co-ordinate set tokra gave to compute these pictures, only 840 instead of 2360 minutes! Even though the ML routine at 828 uses some addresses in the range 673 .. 692 for storing float numbers, it is otherwise fully relocatable.

I also tidied up other parts of the program, added a proper co-ordinate input, and a means to save the completed pictures, resulting in:

Code: Select all

10 FORS=0TO186:READM:POKE828+S,M:NEXT
11 DIMI(2,159),R(159):A=0:B=1:C=2
12 PRINT"{CLR}MANDELBROT SET":PRINT
13 PRINT"X MIN? -2.4{6 LEFT}";:INPUTR0:PRINT"X MAX? .8{4 LEFT}";:INPUTR1:DR=(R1-R0)/160
14 PRINT"Y MIN? -1.25{7 LEFT}";:INPUTJ0:PRINT"Y MAX? 1.25{6 LEFT}";:INPUTJ1:DJ=(J1-J0)/192
15 PRINT"DEPTH? 30{4 LEFT}";:INPUTN:POKE6,N/256:POKE5,N-256*PEEK(6)
16 INPUT"SAVE AS";N$
17 FORS=0TO159:R(S)=R0+DR*S:NEXT
18 POKE36879,14:POKE646,1:@ON:@CLR
19 FORT=0TO191:J=J0+DJ*(191-T):FORS=0TO159:SYS828,R(S),J:I=PEEK(3)+256*PEEK(4):I(C,S)=I
20 IFI<=NTHEN:@1,S,T
21 IFS<2ORT<2THEN30
22 IF@(S-1,T-1)=0THEN30
23 M=I(B,S-1)
24 IFI(B,S-2)<MANDI(B,S)<MTHEN29
25 IFI(A,S-2)<MANDI(C,S)<MTHEN29
26 IFI(C,S-2)<MANDI(A,S)<MTHEN29
27 IFI(A,S-1)<MANDI(C,S-1)<MTHEN29
28 GOTO30
29 @0,S-1,T-1
30 NEXT:Z=A:A=B:B=C:C=Z:NEXT
31 GETA$:IFA$=""THEN31
32 DN=PEEK(186):@SAVE(N$),DN:@RETURN:END
33 :
34 DATA 32,253,206,169,0,133,13,32,138,205,162,181,160,2,32,212,219,162,161,160,2,32
35 DATA 212,219,32,253,206,169,0,133,13,32,138,205,162,186,160,2,32,212,219,162,166,160
36 DATA 2,32,212,219,169,1,133,3,169,0,133,4,169,161,160,2,32,162,219,169,161,160,2,32
37 DATA 40,218,162,171,160,2,32,212,219,169,166,160,2,32,162,219,169,166,160,2,32,40
38 DATA 218,162,176,160,2,32,212,219,169,171,160,2,32,103,216,165,97,201,131,176,75,169
39 DATA 161,160,2,32,162,219,169,166,160,2,32,40,218,230,97,169,186,160,2,32,103,216
40 DATA 162,166,160,2,32,212,219,169,176,160,2,32,162,219,169,171,160,2,32,80,216,169
41 DATA 181,160,2,32,103,216,162,161,160,2,32,212,219,230,3,208,2,230,4,56,165,5,229,3
42 DATA 165,6,229,4,176,133,96
43 :
44 REM ** MG MANDELBROT V2 WRITTEN 2010-06-08 BY MICHAEL KIRCHER
Cheers,

Michael
Last edited by Mike on Thu Feb 20, 2014 4:23 pm, edited 2 times in total.
User avatar
tokra
Vic 20 Scientist
Posts: 1120
Joined: Tue Apr 27, 2010 5:32 pm
Location: Scheessel, Germany

Post by tokra »

Nice! I'm wondering: If you used the usr-function instead of a sys-call and peek would this speed things up further?
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Post by Mike »

The BASIC part makes up for an overall constant time added to the calculation of each pixel.

This is mainly because of the complex display routine, where a lot of checks are made whether a pixel is to re-paint in black, or not. Rather than looking, whether the parameter passing to the variable I could be sped up, I'd possibly take a look at the lines 21 .. 29, trying to optimise these.

If I were really serious about to optimise that constant term, I'd dispense with the BASIC part altogether, because an all-white picture outside the set - where the ML part terminates after one iteration - already needs ~55 minutes, i.e. roughly 1/10 second overhead for each pixel.

On the other hand, the ML main loop now does ~120 iterations per second. That had been the intended optimisation in the first place, reducing the linear factor. For deep zooms, you need high iteration depths, and in that case the constant time of the BASIC part becomes less important.

I already reduced the calculation time of one example from 39 hours down to 14 hours, optimising away the BASIC part then would get it down to 13 hours. ...
User avatar
tokra
Vic 20 Scientist
Posts: 1120
Joined: Tue Apr 27, 2010 5:32 pm
Location: Scheessel, Germany

Multicolor Mandelbrot (104x240)

Post by tokra »

Yesterday I've ported my old multicolor Mandelbrot program to the new resolution of 108x240 - highly un-optimised BASIC-code as always ;-)

http://www.tokra.de/vic/apfel240m.prg

Needed of course is the graphics-library (and 24K RAM):

http://www.tokra.de/vic/208240-24k.prg

here are two example-pics:

http://www.tokra.de/vic/apfel1m
http://www.tokra.de/vic/apfel2m

Image
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Post by Mike »

:D

Now, it shouldn't be a big problem to use the ML routine as drop-in replacement for the lines 600-630 in your program:

As can be seen from the listing above, you just need to poke beforehand the maximum allowed number of iterations 'N' (16-bit!) into the addresses 5/6, then call the routine with SYS828,R,J - where R denotes the real part, J the imaginary part of 'c' in the iterated formula 'z=z²+c'.

The routine then returns with the number of iterations taken as 16-bit number in the addresses 3/4, values from 1..N indicate the point is outside the Mandelbrot set (i.e. paint in colour MOD 3), N+1 means you should paint the pixel in black ("inside" the set <- for that iteration depth).

If any questions remain, just send me a PM.
User avatar
tokra
Vic 20 Scientist
Posts: 1120
Joined: Tue Apr 27, 2010 5:32 pm
Location: Scheessel, Germany

Post by tokra »

Thanks, Mike! Here you go with an improved multicolor-fractal version using your fast machine-language routines. It also uses the new 208x248 resolution in multicolor mode (=104x248) and provides for color rotation when viewing pictures:

http://www.tokra.de/vic/apfel248m.prg

Required is a modified version of the 208x248 graphics libray. Load and run this first!

http://www.tokra.de/vic/208248-24k-a.prg

Here is a demo-picture that nicely showcases the color rotation:

http://www.tokra.de/vic/apfel2m248
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Post by Mike »

Wow! 8)

PM sent. ;)
Post Reply