Prime factorization
Contents
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
You can download the prime factorization source code here