Posted By
RichTW
on 2016-11-23
14:12:04
|  Re: Mandelbrot and Commodore computers
Hi!
I'm the author of the BBC Micro Mandelbrot. Thanks for the kind remarks! Yeah, the speed comes from a couple of things:
- boundary tracing: it maintains a queue of pixels to evaluate, and starts by adding all the pixels on the screen edge. Then for every item in the queue, it evaluates it and its eight neighbours, and if any neighbour is a different colour, it gets added to the queue itself so its neighbours can also be processed. Obviously the screen itself acts as a cache to save evaluating a pixel which has already been drawn. This saves evaluating the insides of big areas, most notably areas "inside" the Mandelbrot set which would take the most iterations to evaluate.
- fast multiply using the difference of two squares method (and the additional optimization of holding a (n-255)^2/4 table). This reduces the multiplication to a simple 16 bit subtract. The values are actually 32 bit, using 29 bit fixed point - the result comes by summing combinations of partial products and performing a final shift to reposition the fixed decimal point. This leads to a further optimization when squaring a value, since some of the partial products are shared. From a rough estimate, I reckoned the 32bit*32bit multiply completes in around 800 cycles, as opposed to the "naive" multiply which would take between 2200 and 3200 cycles, depending on the number of set bits in the multiplicand.
The code currently performs 32 iterations, but this isn't enough when the zoom gets higher - it should really increase the iteration count the higher you zoom. It should also ideally use more fixed fractional bits to allow for greater precision at high zoom. Currently it refuses to let you zoom beyond five steps as the image starts to go wonky.
|
