New demo uploaded: Fancy Mandelbrot Set Zoomed Plot

All aspects of programming on the Commander X16.
SlithyMatt
Posts: 913
Joined: Tue Apr 28, 2020 2:45 am

New demo uploaded: Fancy Mandelbrot Set Zoomed Plot

Post by SlithyMatt »




Fancy Mandelbrot Set Zoomed Plot




View File






Got a day to kill with your X16? Run this BASIC program and generate this 256-color fractal plot. It's zoomed into a deep part of the Mandelbrot Set that is particularly pretty. This plot does up to 355 iterations and is within an area where all points require at least 100 iterations, so the whole 256-color palette is able to be represented, from white for 100 iterations to black for 355 iterations or more.

For fastest results, run in "warp" mode with your emulator:

x16emu -warp -bas x16-mandelbrot-vga-fancy.bas

At 8Mhz, this will take literally all day, but if you have a beefy enough host for your emulator, it can be cranked out in a couple hours.

Enjoy!

From: https://github.com/SlithyMatt/multi-mandlebrot

 

 
x16-mandelbrot-vga-fancy.bas






 
Edmond D
Posts: 489
Joined: Thu Aug 19, 2021 1:42 am

New demo uploaded: Fancy Mandelbrot Set Zoomed Plot

Post by Edmond D »


OK - who'll be the first to optimize the code to run faster?

Ed Minchau
Posts: 503
Joined: Sat Jul 11, 2020 3:30 pm

New demo uploaded: Fancy Mandelbrot Set Zoomed Plot

Post by Ed Minchau »



25 minutes ago, Edmond D said:




OK - who'll be the first to optimize the code to run faster?



Matt already has shown an assembly language version on YouTube,  320x240 pixels took a little over twelve minutes.

Of course, he wrote the code to be clear for his viewers,  not the most efficient code possible. It might be possible to get it under ten minutes. 

Snickers11001001
Posts: 140
Joined: Wed Jan 20, 2021 6:43 pm

New demo uploaded: Fancy Mandelbrot Set Zoomed Plot

Post by Snickers11001001 »



1 hour ago, Edmond D said:




OK - who'll be the first to optimize the code to run faster?



 

 

spacer.png

 

Actually I can't promise anything.   But I'll look at it!     

SlithyMatt
Posts: 913
Joined: Tue Apr 28, 2020 2:45 am

New demo uploaded: Fancy Mandelbrot Set Zoomed Plot

Post by SlithyMatt »


Also note that my assembly code will not work for this without a significant rewrite to the fixed point library. Being this zoomed in means you need much higher precision. You could probably do it with 8.24 fixed point, if you do some precalculation for the X/Y scaling (i.e. creating constants for the X range divided by 320 and the Y range divided by 240), and then I don't think you will need to deal with any numbers larger than 127, but you still need accuracy to the 10e-6 place, at least.

Edmond D
Posts: 489
Joined: Thu Aug 19, 2021 1:42 am

New demo uploaded: Fancy Mandelbrot Set Zoomed Plot

Post by Edmond D »


Perhaps I should have been clearer - optimizing the Basic code. Going to assembler, as SlithyMatt has already shown is going to generate the image in less time. He's pointed out that the fixed point stuff would require serious rework. That effort would be interesting, but not really useful for the average basic programmer.



Rather than take on this project directly, perhaps starting with what can be done with the simple version would be a good start. This approach should avoid the "couple of hours" it takes to complete and be able to be  ported to the fancy version. Here's the video on the "simple" version and the code appears around the 8:30 mark





 



I see Snickers11001001 is interested in the challenge. Given his in-depth and informative thread 


 

I think it would be hard to beat his attempt. 



Also, I'll add in keeping it scoped to the X16 platform, as other platform's Basics most likley are going to have different optimization techniques.

  

SlithyMatt
Posts: 913
Joined: Tue Apr 28, 2020 2:45 am

New demo uploaded: Fancy Mandelbrot Set Zoomed Plot

Post by SlithyMatt »


There are some very low-hanging fruit that I haven't bothered with so far, in the interest of keeping the working, straightforward implementation of the algorithm in BASIC. I don't think any of these will have a huge impact, but they might shave off a bit of time:


  • Line 10: Do a pair of VERA register pokes to set screen resolution to 324x240


  • After line 50: Set up VERA address registers manually for start of bitmap in VRAM ($4000)


    • Then, replace lines 217-230 with a single line: POKE $9F23,I




  • Lines 120, 130: Pre-calculate 0.000036/320 and 0.000027/240


  • After line 160: Calculate X*X and Y*Y


    • Then, use pre-calculated squares for lines 170 and 180




This area of the plot is not symmetrical, so I don't think you can just do mirroring to save a big chunk of time.

Anything else will take some really digging to come up with optimization. The core driver of the time is the math that just needs to happen.

Scott Robison
Posts: 952
Joined: Fri Mar 19, 2021 9:06 pm

New demo uploaded: Fancy Mandelbrot Set Zoomed Plot

Post by Scott Robison »



21 minutes ago, SlithyMatt said:




There are some very low-hanging fruit that I haven't bothered with so far, in the interest of keeping the working, straightforward implementation of the algorithm in BASIC. I don't think any of these will have a huge impact, but they might shave off a bit of time:




  • Line 10: Do a pair of VERA register pokes to set screen resolution to 324x240


  • After line 50: Set up VERA address registers manually for start of bitmap in VRAM ($4000)


    • Then, replace lines 217-230 with a single line: POKE $9F23,I




  • Lines 120, 130: Pre-calculate 0.000036/320 and 0.000027/240


  • After line 160: Calculate X*X and Y*Y


    • Then, use pre-calculated squares for lines 170 and 180






This area of the plot is not symmetrical, so I don't think you can just do mirroring to save a big chunk of time.



Anything else will take some really digging to come up with optimization. The core driver of the time is the math that just needs to happen.



All very valid points. It is one thing to optimize a 32x22 (or whatever) plot so it shaves a few seconds off something that takes a couple minutes. It is quite another to shave a few seconds off a 320x240 plot that takes literal hours to run.

I'm running a solution right now that does all the horrible unreadable tricks to the BASIC code to try to make it faster. I haven't tried timing the original vs this one (mainly because it takes so long; I need to tweak it to time how long it takes to render a random raster to have something that can be timed, just haven't had time to do that yet). But it seems to work. And it is ugly (and I do not like ugly code unless there is a really good reason, evidence to the contrary notwithstanding).

0 SCREEN0:POKE$9F2D,$07:POKE$9F2F,$20:POKE$9F29,$11:GOSUB12

1 YI=0.000027/240:YZ=0.08784:XS=-0.747345:XI=0.000036/320

2 C0=0:C1=1:C2=2:C4=4:CC=100:CH=256:CA=$4000:CB=153:CE=192:CF=320:CG=355

3 CI=239:CJ=319:POKE$9F20,0:POKE$9F21,$40:POKE$9F22,$10:VP=$9F23

4 FORPY=C0TOCI:XZ=XS:FORPX=C0TOCJ:X=C0:Y=C0:FORI=C0TOCG:X2=X*X:Y2=Y*Y

5 IT=I:IFX2+Y2>C4THENI=CG:NEXT:GOTO7

6 Y=C2*X*Y+YZ:X=X2-Y2+XZ:NEXT

7 I=IT-CC:IFI=CHTHENI=C0

8 B=C0:OS=CA:Y=PY:IFY<CBGOTO11

9 IFY=CBTHENIFPX<CEGOTO11

10 B=C1:OS=-CE:Y=PY-CB

11 POKEVP,I:XZ=XZ+XI:NEXT:YZ=YZ+YI:NEXT:END

12 POKE$9F20,0:POKE$9F21,$40:POKE$9F22,$10:VP=$9F23

13 FORI=1TO320*240:POKEVP,0:NEXT:RETURN

I'll provide some quantitative data later measuring time to rasterize one line in each version, but I think the difference will not be great.

SlithyMatt
Posts: 913
Joined: Tue Apr 28, 2020 2:45 am

New demo uploaded: Fancy Mandelbrot Set Zoomed Plot

Post by SlithyMatt »


Good luck with your run! It is difficult to time, especially since "Warp" mode does not give you a consistent speed, so you need to be able to just do 100% speed for the whole run. I see there are still some of the optimizations I listed above not implemented, so you may want to include them, and maybe even ditch the subroutine to clear the screen before plotting.

Scott Robison
Posts: 952
Joined: Fri Mar 19, 2021 9:06 pm

New demo uploaded: Fancy Mandelbrot Set Zoomed Plot

Post by Scott Robison »



2 hours ago, SlithyMatt said:




Good luck with your run! It is difficult to time, especially since "Warp" mode does not give you a consistent speed, so you need to be able to just do 100% speed for the whole run. I see there are still some of the optimizations I listed above not implemented, so you may want to include them, and maybe even ditch the subroutine to clear the screen before plotting.



I think I can judge it even in warp mode as long as I don't use wall clock time but use TI to report the number of jiffies a range of rows takes. I would clear TI to 0 after clearing the screen, then do a range of rows in the middle of the screen.

Really, because the math is the intense part, removing the screen drawing completely would allow timing just the math code. That's the part in need of optimization (in as much as there is a "need" to do anything like this; there is far more utility to your easier to read and understand version than this, this is just "for fun".

Post Reply