Difference between pages "Dartboard PI" and "Prime factorization"

From Mesham
(Difference between pages)
Jump to navigationJump to search
m (8 revisions imported)
 
(Created page with '== Overview == This example will perform prime factorization on a number parallely, to return the prime factors which make up that number. The example uses the primitive communi…')
 
Line 1: Line 1:
−
<metadesc>Mesham is a type oriented programming language allowing the writing of high performance parallel codes which are efficient yet simple to write and maintain</metadesc>
 
 
== Overview ==
 
== Overview ==
  
−
[[Image:dartboard.jpg|thumb|260px|right|Dartboard method to find PI]]
+
This example will perform prime factorization on a number parallely, to return the prime factors which make up that number. The example uses the primitive communication, all reduce. There are actually a number of ways such a result can be obtained - this example is a simple parallel algorithm for this job.  
−
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 ==
 
== Source Code ==
  
−
  #include <maths>
+
  var n:=976; // this is the number to factorize
−
#include <io>
+
  var m:=12; // number of processes
−
#include <string>
+
  var s:Int :: allocated[multiple[]];
−
+
var p;
−
  var m:=64; // number of processes
+
par p from 0 to m - 1
−
   
 
−
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 k:=p;
−
    var n:=0;
+
  var divisor;
−
    for n from 0 to darts - 1 {
+
  var quotient:Int;
−
      var xcoord:=randomnumber(0,1);
+
  while (n > 1)
−
      var ycoord:=randomnumber(0,1);
+
  {
−
      if ((pow(xcoord,2) + pow(ycoord,2)) < 1.0) {
+
      divisor:= getprime[k];
−
          score++; // hit the dartboard!
+
      quotient:= n % divisor;
−
      };
+
      var remainder:= mod[n,divisor];
−
    };
+
      if (remainder == 0)
−
    return score;
+
      {
 +
        n:=quotient;
 +
      } else {
 +
        k:=k + m;
 +
      };
 +
      (s :: allreduce["min"]):=n;
 +
      if ((s==n) && (quotient==n))
 +
      {
 +
        print[divisor,","];
 +
      };
 +
      n:=s;
 +
  };
 
  };
 
  };
  
−
''This code requires at least Mesham version 1.0''
+
== Notes ==
  
−
== Download ==
+
Note how we have typed the quotient to be an integer - this means that the division n % divisor will throw away the remainder. Also, for the assignment s:=n, we have typed s to be an allreduce communication primitive (resulting in the MPI all reduce command.) However, later on we use s as a normal variable in the assignment n:=s due to the typing for the previous assignment being temporary.
  
−
The dartboard method to compute PI source code is located [http://www.mesham.com/downloads/pi.mesh here] a legacy version for Mesham 0.5 can be downloaded [http://www.mesham.com/downloads/pi-0.5.mesh here]
+
As an exercise, the example could be extended so that the user provides the number either by command line arguments or via program input.
  
−
[[Category:Example Codes]]
+
== Download ==

Revision as of 23:07, 10 January 2010

Overview

This example will perform prime factorization on a number parallely, to return the prime factors which make up that number. The example uses the primitive communication, all reduce. There are actually a number of ways such a result can be obtained - this example is a simple parallel algorithm for this job.

Source Code

var n:=976; // this is the number to factorize
var m:=12; // number of processes
var s:Int :: allocated[multiple[]];
var p;
par p from 0 to m - 1
{
  var k:=p;
  var divisor;
  var quotient:Int;
  while (n > 1)
  {
     divisor:= getprime[k];
     quotient:= n % divisor;
     var remainder:= mod[n,divisor];
     if (remainder == 0)
     {
        n:=quotient;
     } else {
        k:=k + m;
     };
     (s :: allreduce["min"]):=n;
     if ((s==n) && (quotient==n))
     {
        print[divisor,","];
     };
     n:=s;
  };
};

Notes

Note how we have typed the quotient to be an integer - this means that the division n % divisor will throw away the remainder. Also, for the assignment s:=n, we have typed s to be an allreduce communication primitive (resulting in the MPI all reduce command.) However, later on we use s as a normal variable in the assignment n:=s due to the typing for the previous assignment being temporary.

As an exercise, the example could be extended so that the user provides the number either by command line arguments or via program input.

Download

Retrieved from ‘http://www.mesham.com/index.php?title=Dartboard_PI&oldid=766’