Prefix sums

Overview

Dartboard method to find PI

The dartboard method to find PI is a simple algorithm to find the value of PI. At this point it must be noted that there are much better methods out there to find PI, however the dartboard method is embarasingly parallel and as such quite simple to parallelise. The basic premise is that you can throw n darts randomly at a round dartboard on a square backing. As each dart is thrown randomly the ratio of darts hitting the board to those landing on the square is equal to the ratio between the two areas - which is PI / 4. Of course, the more darts you simulate throwing at the board, the better the approximation of PI - in our example each process will perform this simulated throwing a number of times, and then each process's approximation of PI is combined and averaged by one of the processes to obtain the result. Very ruffly, this means that with d darts, thrown over r rounds on n processes, the time taken parallely is the time it takes to simulate throwing d * r darts, yet a sequential algorithm would need to simulate throwing d * r * n darts. (We have excluded the consideration of communication costs from the parallel situation to simplify the concept.) Hopefully quite obviously, in the example by changing the number of processes, the number of rounds and the number of darts to throw in each round will directly change the accuracy of the result.

Source Code

var m:=10; // number of processes
var pi:array[Double,m,1]:: allocated[row[] :: horizontal[m] :: single[evendist[]]];
var result:array[Double,m] :: allocated[single[on[0]]];
var mypi:Double;
mypi:=0;
var p;
par p from 0 to m - 1
{
  var darts:=1000; // number of darts to simulate throwing each round
  var rounds:=100; // number of rounds of darts to throw
  var i:=0;
  for i from 0 to rounds
  {
     mypi:= mypi + (4 * (throwdarts[darts] % darts));
  };
  ((pi#p)#0):=(mypi % rounds);
};
result:=pi;
proc 0
{
  var avepi:Double;
  avepi:=0;
  var j:=0;
  for j from 0 to m - 1
  {
     var y:=(result#j);
     avepi:=avepi + y;
  };
  avepi:=avepi % m;
  print["PI = ",avepi,"\n"];
};

function Int throwdarts[var darts]
{
  darts: Int :: allocated[multiple[]];
  var score:=0;
  var n:=0;
  for n from 0 to darts
  {
     var r:=randomnumber[0,1]; // random number between 0 and 1
     var xcoord:=(2 * r) - 1;
     r:=randomnumber[0,1]; // random number between 0 and 1
     var ycoord:=(2 * r) - 1;
     if ((sqr[xcoord] + sqr[ycoord]) < 1)
     {
        score:=score + 1; // hit the dartboard!
     };
  };
  return score;
}; 

Notes

An interesting aside is that we have used a function in this example, yet there is no main function. The throwdarts function will simulate throwing the darts for each round. As already noted in the language documentation, the main function is optional and without it the compiler will set the program entry point to be the start of the source code.

Download

The dartboard method to compute PI source code is located here