** New Frontiers in VIC-Hires-Graphics, Part 5

[Mike]

For the sheer fun of it, I compared your program against my own implementation with MINIGRAFIK, and a later conversion to C.

I could run the VIC versions with ~120x speed within VICE, so the total computation times were bearable even with the last co-ordinate set you gave:

Code: Select all

x_min=0.76461
x_max=0.76498
y_min=0.10056
y_max=0.10082
max_iter=254

At first, my own program, result 160x192 pixels, time: ~2360 minutes:



Then, your program, result 208x240 pixels, time: ~7550 minutes. It's obvious we're using different methods to display the set, even though the math behind that is the same:



On average, my program displays (160x192)/2360 ~= 13.0 pixels/minute, yours does only (208x240)/7550 ~= 6.6 pixels/minute. There might be some room for improvement , but anyway here's the C version, 800x576 pixels, 1000 iterations (to get deeper into the "black holes" visible above), time on PC: <1 second:



Cheers,

Michael

[tokra]

I remember copying the calculating routine from some 64er article or program back then since I just have a bare idea how it works. The difference must be in the pixel-set routine:

Code: Select all

640 ifn-int(n/2)*2=1thengosub1200

- apparantly this not only sets a pixel within the mandelbrot-set but also outside for some cases, leading to the "pipes" you will see in many of the pictures.

Maybe the calculating routine can be translated to assembler. It's just a few lines of BASIC-code and it would be an interesting to see how this can be done in assembler.

It's amazing to see that a PC today can do the same in under a second at much higher resolution. Back in 1993 my old Commodore 128 would need WEEKS for some sets calculated at the then insane resolution of 720x700 - that's why I added a save-and-continue option to that program...

Torsten

[matsondawson]

Heh, even java (1.5) does it in less than a second...

http://www.mdawson.net/mandelbrotApplet.php

[Mike]

Heh, even java (1.5) does it in less than a second ...

"It" of course requires you specifying co-ordinate set, maximum iteration depth, and resolution used for the picture. I made a try with your Java version, and indeed it fared quite well, though I wouldn't say it took less than 1 second in that case:



And, the pictures even get more interesting if you're zooming into regions which require more than 1000 iterations so you don't get an all-black picture.

BTW, my C version has an optimisation built-in which avoids calculating "into" the regions with iterations greater than the specified maximum: it's a simple floodfill algorithm at work, which fills in from all points of the picture border, and then regards all points with 'iter=max_iter' as boundary. This works because the Mandelbrot set is 'simply connected': it doesn't have holes inside which aren't part of the set, so nothing is missed out.

apparantly this not only sets a pixel within the mandelbrot-set but also outside for some cases, leading to the "pipes" you will see in many of the pictures.

That region really isn't part of the main set, it rather is its 'decoration' outside - if you'd adopt the convention of painting all 'escaping' pixels in white, and really only points within the Mandelbrot set black, you'd get a near all-white picture at an iteration depth of 1000, as could be guessed from the Java-drawn picture above - except maybe for some lucky hits on satellites of the main set.

My display routine zeroes in on these decorations by re-painting the pixel black when a point of a comparatively high iteration depth is surrounded by two pixels of lower iteration depths in at least one of the horizontal, vertical, or the two diagonal directions.

Looking at your main loop:

Code: Select all

600 ifd>=4then640 
610 x=r:y=i:r=x*x-y*y+a:i=2*x*y+b:d=r*r+i*i:n=n+1 
620 ifn=nmthen650 
630 goto600 

compared to mine:

Code: Select all

17 FORI=1TON:X2=X*X:Y2=Y*Y:IFX2+Y2<4THENXY=X*Y:X=X2-Y2+R:Y=XY+XY+J:NEXT

gives some hints (one thing beforehand - a NEXTS further down in my program pops the pending 'NEXTI' off the stack if the FOR loop in line 17 is left prematurely ...):

Using 3 multiplications instead of 6 probably accounts for most of the speed difference, but then I also did an early assignment to most of the variables used within the main loop (not necessary for I, and N as BASIC holds a pointer to I, and reads N only once); finally '630 goto600' requires a scan from the beginning of the program to where 600 is, this would be slightly faster were the loop located more at the top - again, a FOR stores a pointer to the instruction immediately after the FOR, so in my case it wouldn't make a difference.

Maybe the calculating routine can be translated to assembler.

The arithmetic within CBM BASIC is really not something to be embarrased about regarding speed, the routines are quite efficient indeed for providing a 32-bit mantissa (hence 9 significant digits).

One could reduce the precision to 24 or even 16 bits, but then you can't zoom in beyond the point where the details of the set just become interesting enough ...

Translating the main loop to assembler (calling the arithmetic routines within BASIC directly) would indeed at least relieve the loop to scan the expressions, and doing the variable look-up again, and again. Which might speed it up by another 20-30%. I'll take a look at it over the next days - maybe I have a prototype running the next weekend. [*]

Greetings,

Michael

P.S.: Edit: [*] well it didn't take that long. See here.