Difference between revisions of "Dartboard PI"

From Mesham
Jump to navigationJump to search
(Source Code)
Line 39: Line 39:
 
  };
 
  };
 
   
 
   
  function Int throwdarts(var darts:Int)
+
  function Double throwdarts(var darts:Int)
 
  {
 
  {
     var score:=0;
+
     var score:Double;
 
     var n:=0;
 
     var n:=0;
 
     for n from 0 to darts - 1 {
 
     for n from 0 to darts - 1 {

Revision as of 13:12, 1 February 2013

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

#include <maths>
#include <io>
#include <string>

var m:=64; // number of processes

function void main() {
   var calculatedPi:array[Double,m]:: allocated[single[on[0]]];
   var mypi:Double;
   var p;
   par p from 0 to m - 1 {
      var darts:=10000; // number of darts to simulate throwing each round
      var rounds:=100; // number of rounds of darts to throw
      var i;
      for i from 0 to rounds - 1 {
         mypi:=mypi + (4.0 * (throwdarts(darts) / darts));
      };
      mypi:=mypi / rounds;
      calculatedPi[p]:=mypi;
   };
   sync;
   proc 0 {
      var avepi:Double;
      var i;
      for i from 0 to m - 1 {     			
         avepi:=avepi + calculatedPi[i];
      };
      avepi:=avepi / m;
      print(dtostring(avepi, "%.2f")+"\n");
   };
};

function Double throwdarts(var darts:Int)
{
   var score:Double;
   var n:=0;
   for n from 0 to darts - 1 {
      var xcoord:=randomnumber(0,1);
      var ycoord:=randomnumber(0,1);
      if ((pow(xcoord,2) + pow(ycoord,2)) < 1.0) {
         score++; // hit the dartboard!
      };
   };
   return score;
};

This code requires at least Mesham version 1.0

Download

The dartboard method to compute PI source code is located here a legacy version for Mesham 0.5 can be downloaded here