I'm sure everybody who has ever played around with computer programming has at one point or another written some code that draws the Mandelbrot set. It turns out that there's a cool way to calculate π in there too.

The Mandelbrot

If you've not implemented complex numbers before they're fairly simple. A complex number is a binary tuple where the first number is real and the second imaginary, (x, yi). i is the square root of -1. Squaring these numbers is fairly simple:

let sqc (r, i) = ( r * r - i * i, 2 * r * i )

And adding them is even simpler:

let add (r1, i1) (r2, i2) = (r1 + r2, i1 + i2)

The basics of the sequence are to convert the x and y screen position into a complex number over the range -1 to 1 on each axis and then keep squaring and adding:

let step o v = add o (sqc v)

Where o is the original number and v is the result of the last iteration step. The steps are always started with a point at the origin, so at step 0 the value is 0, and at step 1 the value is the complex number we're calculating for.

The normal way to determine if a given location is outside the Mandelbrot is to keep doing the calculation step until the distance from the origin is more than 2 — once we're more than 2 away from the origin then we know that the calculation will keep producing ever bigger numbers. Inside the set the iteration will never complete as the calculation goes into an infinite loop. The distance from the origin is done in the obvious way using Pythagoras' theorem (but now we're not taking the y as a complex number, it's simply a distance along the axis):

let length (r, i) = sqrt (r * r + i * i)

Calculate π

The calculation involves using complex numbers where the real component is -0.75 and is really simple. You decide how accurately you want to calculate π, say we want ±0.2 (the error term), we then do the steps from the Mandelbrot counting how many steps we need until the distance goes to 2 or more. π is the number of steps times our error term takes to get to a distance of 2 or more.

Doing the calculation we get 15 steps so π is 15 × 0.2 ±0.2. We can reduce the error term to get more accurate results.

There are 1609 meters to a mile and the Golden Ratio is about 1.618. This is just close enough to be able to use consecutive numbers in the Fibonacci sequence to convert between miles and kilometres. It works because consecutive numbers in the Fibonacci sequence approximate the Golden Ratio.

I.e., if 5 is input this is the equivalent of 8 kilometres if the 5 is taken as miles and is equivalent to around 3 miles if the 5 is taken as kilometres.

If we have to convert a number that isn't part of the sequence then we will need to find numbers in the sequence that add up to the number we want to convert.

I.e. for 100 we would want to find numbers in the Fibonacci sequence that add up to 100, convert them and then add up the results. So, 100 = 89 + 8 + 3:

• 89 is 55 miles and 144km.
• 8 is 5 miles and 13km.
• 3 is 2 miles and 5km.

This means that 100 is 55 + 5 + 2 = 62 miles and 144 + 13 + 5 = 162km.

100 is actually 62.137… miles so the error is about 0.2%. 100 is also 160.9344 km so the error in the other direction is about 0.7%.

The next version of Fost has just been released and tagged in our repository.

There has been major work on the build system and the internet library as well as a large number of other small and large changes.

• For users of Karmic it is now possible to use the version of Boost that comes from the package repository and we'll very soon be supporting a central Boost location on Windows as well.
• Within fost-inet we've added POP3 mailbox support and made big improvements to the URL parsing.
• The testing is been refactored out so that only those that don't rely on external resources are run during most builds.
• On Windows the MFC/ATL requirement is now optional (off by default and can be turned on by adding have_mfc=yes to the build options for any of the libraries). This makes the libraries usable with Microsoft's Express compilers.

We think that this version should be better on OS/X as well. By the next release we should have better access to Macintosh machines so the Mac support should be more stable in future too.

Next steps

We'll be working more on the documentation and examples and we'll be making it simpler to use the libraries, especially on Ubuntu where the use of the built in Boost packages now means we can package the Fost libraries and development files as well.

We are also planning on finalising the JSON API so that we can declare that part stable and get it documented.

4.10.03.x is due out on March 21st, 2010.

Subversion locations

The tagged release is at the following locations:

• http://svn.felspar.com/public/fost-base/tags/4.09.12.37887/
• http://svn.felspar.com/public/fost-internet/tags/4.09.12.37887/
• http://svn.felspar.com/public/fost-meta/tags/4.09.12.37887/
• http://svn.felspar.com/public/fost-orm/tags/4.09.12.37887/
• http://svn.felspar.com/public/fost-postgres/tags/4.09.12.37887/
• http://svn.felspar.com/public/fost-py/tags/4.09.12.37887/
• http://svn.felspar.com/public/fost-windows/tags/4.09.12.37887/

In detail

• Added more documentation and made some small refactorings due to that.
• The spider has been refactored. Whether it will follow redirects is now configurable.
• Query strings are now used properly when fetching resources using the HTTP agent.
• Query strings are now handled properly when URLs are joined using the Python language bindings.
• Started to sketch out how the timezones (based on zoneinfo) might be handled.
• Added a POP3 mailbox processing API.
• Fixed up the MIME text_body part's handling of the Content-Type header when it is being loaded up from somewhere else.
• Added a MIME header API for setting sub-values
• Changed the instance creation API in the O/RM library to use an auto_ptr to make the ownership transfer explicit.
• Python JSON handling is now able to convert sets and frozen sets to fostlib::json instances (they appear as lists/arrays).
• The old fostlib::utf8string (a typedef to std::string) is now replaced by a proper tagged string implementation, fostlib::utf8_string. This makes the use of UTF8 strings safer and the encoding/decoding of the strings explicit.
• A fix to the spider so that it can properly handle non-200 status codes when running tests.
• A number of missing characters have been added to the URL parser, as well as support for query strings.
• The URL parser is now less strict about what it accepts over what it will build.
• The AWS s3put example no longer tries to run a test. The security for this won't work for other people building Fost.
• There is a new fost-install-to-directory rule that gives greater control over the install locations.
• There is a new fost-lib-autotest rule that automatically finds tests and source code and makes sure the tests are run. Various targets have been ported to this new rule.
• The output files are tagged for debug builds, i.e. their names change for debug builds.
• Much of the build system is less dependant on the location of the build files.
• There is a new build option of have_mfc=yes that can be used to enable MFC/ATL support which is now off by default.
• There should now be cleaner handling of programs that are stopped with CTRL-C
• The WINVER macro is now only defined if not already defined.
• The compile scripts (Windows) no longer assume the toolset.
• Various parts of the JSON API will now accept narrow and wide character literals as expected.
• A memory leak has been plugged for when a dynamic link library fails to load on Linux and Macs.
• All exceptions can now be coerced to strings.
• fostlib::ascii_string instances are now properly checked on platforms where char is unsigned.
• boost::filesystem::wpath instances are now properly coercable to and from strings and JSON.
• The DLL path is now set on executables on Unix. This should remove (or atleast reduce) the requirement to set the LD_LIBRARY_PATH.
• Fixed the JSON pretty printing example in fost-base.

Sorry for the lack of puzzle last time — I was flying to Pusan (Korea) and didn't get time to put anything together.

Anyway, there's always some interest when somebody posts not only a puzzle, but also offers a cash reward for solving it. This is what is happening over at the Computational Complexity blog where there's $289 for managing to solve a graph colouring problem.

This sort of map colouring problem is quite well known in many computer circles as the original four colour problem was the first major mathematical proof that was conducted with the help of a computer program.

We can represent the four colours by the numbers zero to three and simplify the problem somewhat

If we start off with a 1 x 1 grid then we only need 1 colour. A 2 x 2 grid requires 2 colours (the squares in opposite corners aren't adjacent so can have the same colour). As the we increase the size of the grid then the number of colours we need should go up, but will never exceed four.

The output of the program should be m lines of n digits that represent the colours that are used. I.e. for the 2 x 2 case we can have:

0 1
1 0

I.e. the program starts by placing colour 0 somewhere, then it places colour 1, then colour 2 etc. When it's placed colour 3 it needs to place 0 again. If n x m is divisible by four then there should be equal numbers of each colour. For 2 x 2 we might have:

0 1
2 3

I.e. the above solution produces a total of 24 (1 + 23), but if we move the digits around a bit we can get:

0 3
1 2

This produces a sum of 15 so is better.

Just posting the sums is enough.

Mike has put together a different sort of obfuscatory challenge. You need a fairly modern browser (and possibly a bit of luck as well unless you have Safari) to get it working.

You can see the challenge here.