Difference between pages "Dartboard PI" and "File:2gb.jpg"

From Mesham
(Difference between pages)
Jump to navigationJump to search
(Download)
 
(Fast Fourier Transformation with 2GB of data)
 
Line 1: Line 1:
== Overview ==
+
Fast Fourier Transformation with 2GB of data
 
 
[[Image:dartboard.jpg|thumb|260px|right|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 [http://www.mesham.com/downloads/pi.mesh here]
 

Revision as of 17:52, 11 January 2010

Fast Fourier Transformation with 2GB of data