Monte Carlo for PI

Following the algorithms line, there’s one I love to see in action, and that’s the PI calculator using monte carlo.

Using the arctan formula is too simple and not funny at all, we need something less obvious.

So, get a disk of radius 1, the area of that disk is PI * R² but, as the R = 1, the area is PI. You could integrate the function y = sqrt(1 – x²) from -1 to 1 and multiply by 2 and voilá, you have PI. There are loads of integration methods available (brute-force, trapezoid, Simpson, Romberg) and the later generate very acurate results but that’s still not funny.

So, let’s integrate the disk on a different way: Monte Carlo. This method, named (and popularized) by guys like Enrico Fermi, Metropolis and John von Neumann is based on randomness. You already know that, to integrate a function you have to sum every “point” from start to finish. Monte Carlo assumes that it makes no difference if you do it sequential or random. (what makes a lot of sense to me ;).

The algorithm was proved to converge to the correct solution but that’s not all, it was proved that the accuracy is independent of the dimension of your space!! So, if you have a disk to integrate on 2 or a one billion dimensions space, the same accuracy will be achieved with the same number of points.

With an image it’d be easier to understand but try to draw a circumference using points. If you put 6 points, one after the other you’ll have a little arc. But, if you put it equally spaced on the circumference you’ll have a hexagon, which is much closer to a circumference than a little arc.

If you have random points, the probability of having something spaced rather than a little arc is much bigger, so, using random points you have a better result earlier.

Well, back to the PI assuming we don’t know yet the area of that disk. You do know the area of a square of side 2, which is 4. So, if you put such square centred behind the disk it’ll fit perfectly (the diameter of the disk is also 2) you’ll see the four corners of the square. If you start shooting at that target, the probability of hitting the disk is proportional to it’s area related to the square’s area.

So, 4 is to the area of the disk as the total number of hits is to the number of hits on the disk. That’s it. Start shooting, divide the disk hits by the total and you have the area of the disk, which is PI.

The source code is sooo simple anyone can understand, really, and it’s here: PIMC

State Pattern and Sudoku Glasses

I’m playing with some new algos these days: State Patterns and Spin Glasses.

The state pattern is an object oriented class structure that allow you to create very complex state machines (as complex as you want) without having to maintain a huge interstate matrix and have 110% of chance to break the code later. Check the example at my State Pattern small page.

Using this approach I could drastically reduce the complexity of an error log parser and also it’s 10 times faster to run and compile!

The other algo is called spin glass and it’s about dynamic problems, most of the time insoluble by any direct means, and some times insoluble by any means. The problem I’m trying to solve is far too simple and exact: a sudoku.

I though about using spin glasses because for every insertion, it removes lots of possibilities and reduce drastically the number of options. Also, because it keeps a global value, the sum of each row, column and block, it’s straightforward to check when a value was found. Check my little page about sudoku solver.

Using this approach I could solve 10.000 sudoku puzzles in less than one second on a mere pentium 4 machine.

The idea behind State Pattern is to create a generic state (the interface) that is attached to the State Controller. There is no state change list and no switch/case statement on this pattern, only states.

The state knows two things: what to do now and when to change to the next state(s). So, the interface have two important methods: run, that do whatever is needed and newState that returns the new state or itself, in case of no change.

As simple as that, it’s very powerful and extremely fast!

Sudoku glasses is also very simple: It’s a grid or 9x9x9 which’s a cube of spins (0, -1 or a positive number bigger than 8, say 9). It can be seen as a set of 9 sudoku boards, one for each value (1-9). Every time you ‘set’ a value you put the big integer on it and -1 on all cells it blocks (ie. it’s row, col and block).

It’s simple to see that if the sum of all members of the row/col/block is between 0 and -8 it’s not complete yet (ie. some zeros still there). If the sum is -8 means that there’s 8 times -1 and one zero, which means that cell is defined. When you put 9 on it the sum goes bigger than zero, which means it’s solved and marked.