Difference between pages "Mesham" and "Prime factorization"

From Mesham
(Difference between pages)
Jump to navigationJump to search
 
m (6 revisions imported)
 
Line 1: Line 1:
<div id="Mesham"></div> __NOTOC__ __NOEDITSECTION__
+
<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 ==
  
<!-- Welcome box -->
+
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.
{{Welcome}}
 
{{Help Us}}
 
<!-- Table stuff -->
 
{| style="width: 100%; margin: 0; padding: 0; border: 0; border-collapse: collapse;"
 
| style="padding: 0; width: 25%; vertical-align: top;" |
 
  
<!-- First column -->
+
== Source Code ==
{{Box|subject= OS Development}}
 
{{Box|subject= Resources}}
 
  
| style="padding: 0 0 0 10px; width: 25%; vertical-align: top;" |
+
#include <io>
 +
#include <string>
 +
#include <maths>
 +
 +
var n:=976; // this is the number to factorize
 +
var m:=10; // number of processes to use
 +
var s:Int :: allocated[multiple[]];
 +
function void main() {
 +
    var p;
 +
    par p from 0 to m - 1 {
 +
      var k:=p;
 +
      var divisor;
 +
      var quotient;
 +
      while (n > 1) {
 +
          divisor:= getprime(k);
 +
          quotient:= n / divisor;
 +
          var remainder:= n % divisor;
 +
          if (remainder == 0) {
 +
            n:=quotient;
 +
          } else {
 +
            k:=k + m;
 +
          };
 +
          s :: allreduce["min"]:=n;
 +
          if ((s==n) && (quotient==n)) {
 +
            print(itostring(divisor)+"\n");
 +
          };
 +
          n:=s;
 +
      };
 +
    };
 +
};
  
<!-- Second column -->
+
''This code requires at least Mesham version 1.0''
{{Box|subject= Languages}}
 
{{Box|subject= Tools}}
 
  
| style="padding: 0 0 0 10px; width: 25%; vertical-align: top;" |
+
== Notes ==
  
<!-- Third column -->
+
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.
{{Box|subject= Hardware}}
 
  
| style="padding: 0 0 0 10px; width: 25%; vertical-align: top;" |
+
As an exercise, the example could be extended so that the user provides the number either by command line arguments or via program input.
  
<!-- Forth column -->
+
== Download ==
{{Box|subject= OS theory}}
 
  
|}
+
You can download the prime factorization source code [http://www.mesham.com/downloads/fact.mesh here] and a legacy version for Mesham 0.5 is also available [http://www.mesham.com/downloads/fact-0.5.mesh here]
 +
 
 +
[[Category:Example Codes]]

Latest revision as of 15:44, 15 April 2019

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

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

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

This code requires at least Mesham version 1.0

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

You can download the prime factorization source code here and a legacy version for Mesham 0.5 is also available here