Mandlebrot rendering optimization method

Mandlebrot rendering optimization method

I thought of a new optimization for rendering the Mandlebrot set on a computer screen.  It involves prioritizing pixels based on whether or not their color has changed since the last iteration, and it is useful for real-time rendering.

Consider an unrendered 1,000x1,000 px canvas.  On it are 1,000,000 pixels to calculate.  The traditional naive method is to iterate over every pixel and stop only when the dwell is reached or the orbit escapes.  Such a method is computationally costly when the dwell is considerably large and there are large portions of pixels in the set (i.e. traditionally black pixels) within the current canvas.  One purpose of real-time rendering is to see just outside the set, not where the set is per se.  This new rendering method will algorithmically priorotize colored pixels to calculate in a computationally efficient manner to tend to render the bands first before spending time verifying that pixels in the set will cap out at the current dwell.

For the purposes of illustration, let us also assume that our 1000x1000 canvas is centered at the origin with horizontal and vertical ranges of [-2,2].

My optimization algorithm will start with the assumption that all pixels are in the same band, so we will only calculate one iteration of the top-left-most pixel.

This is easy to display, as the point (-2,2) escapes before the first iteration:

Next, we break down this "one" pixel into 4 sub-pixels and check to see what their color is.  As a result, you get a 2x2 Mandelbrot set render:

Next, of the pixels we just rendered, we only break them down into their subpixels if they are a different color from their parent.  So we will calculate the children of the top-right, bottom-left, and bottom-right, but ignore the top-left since it's the same color as last time.  Note that this is a naive implementation of the algorithm for illustrative purposes.  The next run gives a 4x4 render of the Mandelbrot set:

As you can see, we are already starting to see the shape of the set, and we've only calculated 13 pixels.  The next version will only select those smaller pixels whose color is different from its parent and break them down to get a 16x16 render:

As a result of selectively ignoring stagnant pixels, we can rush to render those regions which are interesting.  Now for 4 iterations this particular algorithm isn't any more impressive than if you simply rendered pixels in subchunks with no prioritizing, but this method starts to shine in areas where there are large regions of black, like a zoom-in to a mini-mandelbrot.

The details of the prioritizing process is left as an exercise to developers, but a few notes may aid the process.

1. It may be useful to only deprioritize regions for a few iterations, as seen in the example above, a naive deprioritization will lead to interesting areas being left unrendered until the end.
2. Be sure to calculate each pixel all the way to its dwell, as coupling the dwell with the current iteration in the render will result in mandelbrot set members to be focused on.

Got it working!

You can see that it very quickly finds a lot of the noisy parts of the image, and defers computation for areas which have neighboring colors that are the same.

Update:  Already got it quite a bit faster!

The big blue area is where the dwell is maxed out.

Why the 25% Bitcoin Attack is not a Problem

Recently, there was a paper which outlined a vulnerability in the Bitcoin protocol.  This paper claimed that with a share of the computing power of the network adding up to only 25%, "Selfish" Miners could take advantage of the rest of the network and take more bitcoins from the block reward than their fair share.

The paper is wrong.  They fail to take into consideration the extra amount of time it takes to generate blocks.

Let's assume for a moment that a pool has 25% of the mining power.  If this is true, then they expect to finish 25% of the blocks everyday, which yields an expected daily income of 900 BTC from block rewards.  While it is true that more or fewer blocks can be finished in one day, the assumption of the 25% computing power share renders that irrelevant.

The paper states "We assume that miners are rational; that is, they try to maximize their revenue, and may deviate from the protocol to do so."

If this is true, then a strategy which yields an expected daily income of less than 900 BTC would not be followed by a rational miner, selfish or not.

This is a simplification of Selfish Mining.  Circles are blocks and vertices are the periods of time between completed blocks.  The paper assumes that each round takes 10 minutes.  This is false.  By this false assumption, the expected daily income of a Selfish Miner is 1,008 BTC, which we can see is bigger than 900 BTC.

As said before, the paper does not take into account the extra time for blocks to finish if you're not following the protocol in this manner.

Here's what the strategy actually yields:

The 3 minutes and 20 seconds extra on the 4th block is when the 25% selfish pool is waiting for the rest of the network to catch up in order to cause a fork event.  The 6 extra minutes on the 5th block is because on average, they will force half of the network to work on their "false" fork.

While they expect to receive 25 BTC on the 4th block, they can only expect to receive 40% of the revenue from the 5th block.  Not only this, but 37.5% of the time they won't get anything because the public block finished first, causing everyone to continue to work on it.

As a result, their expected earnings per event are 21.875 BTC, and due to the extra time, we can expect ~24.27 of these events to occur per day, which leaves an expected daily income of ~530.90 BTC, which is ~369.10 BTC less than if they were honest.

Conclusion:  Miners can be expected to not follow this strategy since it yields less income.

Comment? Concerns?  Leave a comment below.

tl;dr Miners lose by following the "Selfish Mining" technique by about a 41% decrease in expected income if they control 25% of the network.

Why Ruby’s Binary Search is Meh

As of Ruby 2.0.0, the Array#bsearch and Range#bsearch instance methods have been added to do binary searching within an array or a range.

While this awesome algorithm is much welcomed, Ruby has it implemented in a slightly broken manner, (in my probably silly opinion).

First, let’s look at how it works, and by works I mean works in the way expected and produces a meaningful and reasonable result.

some_array = [ 0, 1, 4, 7, 10, 15, 99, 100 ]

Let’s try to find the first element in the array that is bigger than or equal to 72.

some_array.bsearch { |i| i >= 72 }

#=> 99

Cool!  And if the algo is running the way it should, that took 3 iterations, instead of the 7 iterations a linear search might take.

Now, this only works if the array is sorted, which is a requirement of the binary search algorithm in general.  Let’s see why:

The binary search algorithm works as fast as it does because it makes assumptions.  It assumes that the values are in order, because it uses this assumption to “throw away” portions of the collection at a time.  In our example, it did something like this:

[ 0, 1, 4, 7, 10, 15, 99, 100 ]
hmm, some_array is 8 elements large. I’m gonna check the middle first.

okay, the middle has the number 10.  well, 10 is NOT greater than or equal to 72, and since everything is in order, everything below it is useless too, so my new array is… 
[ 15, 99, 100 ]

okay, this is 3 values large, so I’ll check the middle again

99 IS larger than or equal to 72, so everything bigger than it can suck it!
New array is:

[ 15 ] 
well, the only element in this one is LESS than 72, so that 99 was the right answer!

Okay, this works nicely.  But what if I set the condition to be the last guy less than 7?

That should be 4, the third element of the array.

Unfortunately, you can’t tell it to give you “the last element which…”, but only “the first element which…”

And even if you try to use this logic, you’ll get unexpected results.

Let’s try to find the first guy less than 7.  Should be 0, right?

[ 0, 1, 4, 7, 10, 15, 99, 100 ] 
hmm, some_array is 8 elements large. I’m gonna check the middle first.

okay, the middle has the number 10.  well, 10 is NOT less than 7, and since everything is in order, everything below it is useless too, so my new array is… 
[ 15, 99, 100 ]

Wait, wha…?  It still threw away the bottom half!  That’s where the 0 was...

[ 15, 99, 100 ]

okay, this is 3 values large, so I’ll check the middle again

99 is NOT less than 7, so everything bigger than it can suck it!
New array is:

[ 15 ] 
well, the only element in this one is BIGGER 7, so there is no right answer!

I’d better tell the user the answer is nil.

Okay, that’s not quite what I wanted.  Is there a better way to do this?  Should the search ‘save’ the other half and look through it if the right hand fails?  Should there be other bsearch-type methods that work a little differently (like bsearch_max or something)?

Feel free to comment below to tell me why I'm wrong or what should be done.

Cheers!