Softwire Speed Coding Challenge – Question 2 Discussion


30 April 2012, by

previous article in series

So, in our last speed coding post, we set you the second question in our challenge. Here it is again, just to remind you!

Question 2 – Write a program to draw part of the Mandelbrot Set

Define:

     $$begin{array}{rcl} z_1 & = & z \ z_{i+1} & = & z_i^2 + z \ end{array}$$

where z is a complex number. Equivalently you can forget about complex numbers and use 2d coordinates:

     $$begin{array}{rcl} x_1 & = & x \ y_1 & = &  y \ x_{i+1} & = &  x_i^2 - y_i^2 + x \ y_{i+1} & = &  2x_i y_i + y \ end{array}$$

For our purposes, points $z$ (or ($x$,$y$)) in the complex plane are said to be in the Mandelbrot set if:

     $$left| (z_{100}) right| leq 2.0$$

or, equivalently:

     $$sqrt{x_{100}^2 + y_{100}^2} leq 2.0$$

Your picture should be 800×600 pixels (you may use 200×150 pixels if you are using Ruby or Python).  It should have its left top co-ordinate at (-1.14183, 0.47056) and its right bottom co-ordinate at (-0.60999,-0.06128), and it should draw pixels which are in the Mandlebrot Set as white, and those that are not as black.

Hopefully you tried to come up with a solution yourself! If you did, you should have ended up with a picture looking something like this:

 

The Mandelbrot Set

Does it match with your picture? It certainly matched with Matthew‘s; he came up with this solution in a time of 17 minutes, just pipping 4 other solutions to top spot! (He really is a bit good, isn’t he)!

Winning Solution – Submitted by Matthew Richards:

static void Main(string[] args)
{
  var drawing = new Bitmap(800, 600);

  double left = -1.14183;
  double right = -0.60999;
  double top = 0.47056;
  double bottom = -0.06128;

  double xStep = (right - left)/800;
  double yStep = (bottom - top)/600;

  for (int i = 0; i < 800; i++)
  {
    for (int j = 0; j < 600;j++)
    {
      double xCoord = left + (xStep*i);
      double yCoord = top + (yStep*j);

      if (Mandel(xCoord, yCoord) <= 2.0)
      {
        drawing.SetPixel(i, j, Color.White);
      }
      else
      {
        drawing.SetPixel(i, j, Color.Black);
      }
    }
  }

  drawing.Save(@"d:testmandel.bmp");
}

static double Mandel(double x, double y)
{
  double xOrig = x;
  double yOrig = y;

  for (int i=2; i<=100;i++)
  {
    double xNext = (x * x) - (y * y) + xOrig;
    double yNext = (2 * x * y) + yOrig;

    x = xNext;
    y = yNext;
  }

  return Math.Sqrt((x*x) + (y*y));
}

Comments on the Winning Solution

There wasn’t a huge amount about this winning solution that was particularly special; the majority of answers followed the same basic route. Matthew has kept things nice and simple though, which can only improve his efficiency, both in terms of coding and debugging if there are issues!

General Comments

  • C# has libraries which make certain aspects of this much easier. In particular, there are libraries for complex numbers (System.Numeric.Complex) and also for co-ordinates (System.Drawing.Point). These are reasonably well known libraries if you’ve worked in either of the relevant fields before; wish I’d known about this second one though, it would have saved me a bit of time!
  • Richard Bradley (the setter of the question) gave a big hint to use x/y co-ordinates rather than complex numbers when trying to figure out the solution, most people took his advice and went the quicker way with this (it is a speed coding challenge, so that does make sense)!
  • A couple of people solved this using just one function, which dealt with all of the logic. As Matthew has shown above, code is much easier to understand (and generally much easier to write) if you split things up a bit and use helper functions.
  • Finally, a very small thing. It is slightly quicker/easier to test for x > 4, rather than Math.Sqrt(x) > 2. x^2 + y^2 is always positive for non-complex x and y – no need to check for values < -4.

Bonus Points

Some bonus style points were available for this task, for going beyond the spec of the question and making a prettier, more colourful version of the picture, based on a sliding scale (i.e. setting a colour based on the distance from 2, rather than making it an explicit cut-off). Joe Lee-Moyet got one of three official bonus points (along with Iain Monro and Rupert Wood) for creating this image:

A prettier version

That’s that for question 2. Let us know how you did with this one in the comments and we’ll post question 3 shortly!

next article in series

Tags: , , , , ,

Categories: Softwire, Technical

«
»

3 Responses to “Softwire Speed Coding Challenge – Question 2 Discussion”

  1. configurator says:

    I found it very easy with complex numbers, and it requires less code than it would with coordinates – why are they quicker here than complex numbers, assuming library support for those?

  2. I think the x/y version is likely to run quicker, as there will be fewer method calls and fewer variables involved, so it will be much easier for the compiler to optimise the machine code. Think of the x/y approach as an “inlined” version of the complex number approach. (I haven’t measured this, and my intuition may be wrong.)

    However, if there is a complex number lib you are familiar with, then you are right that it may well be quicker to code the complex version. It also looks nicer. It’s a tradeoff, as ususal.

    I mostly included the x/y version as a hint in the question because I knew most people wouldn’t be familiar with any complex number libs, but that a few people would be, and I didn’t want the question to be a test of that prior knowledge.

  3. Rupert Wood says:

    There’s actually one new in .NET 4: System.Numerics.Complex

    http://msdn.microsoft.com/en-us/library/system.numerics.complex.aspx

    although I didn’t know about it on the night. It doesn’t have a MagnitudeSquared property, though, so if you want to avoid the sqrt for the magnitude test then you’ll need to add that yourself. I expect we all used the x-y approach because it’s simple enough and easy to understand.


Leave a Reply

* Mandatory fields


× eight = 24

Submit Comment