Parallel calculations

From Rosetta Code
Jump to: navigation, search
Task
Parallel calculations
You are encouraged to solve this task according to the task description, using any language you may know.

Many programming languages allow you to specify computations to be run in parallel. While Concurrent computing is focused on concurrency, the purpose of this task is to distribute time-consuming calculations on as many CPUs as possible.

Assume we have a collection of numbers, and want to find the one with the largest minimal prime factor (that is, the one that contains relatively large factors). To speed up the search, the factorization should be done in parallel using separate threads or processes, to take advantage of multi-core CPUs.

Show how this can be formulated in your language. Parallelize the factorization of those numbers, then search the returned list of numbers and factors for the largest minimal factor, and return that number and its prime factors.

For the prime number decomposition you may use the solution of the Prime decomposition task.

Contents

[edit] Ada

I took the version from Prime decomposition and adjusted it to use tasks.

prime_numbers.ads:

generic
type Number is private;
Zero : Number;
One  : Number;
Two  : Number;
with function Image (X : Number) return String is <>;
with function "+" (X, Y : Number) return Number is <>;
with function "/" (X, Y : Number) return Number is <>;
with function "mod" (X, Y : Number) return Number is <>;
with function ">=" (X, Y : Number) return Boolean is <>;
package Prime_Numbers is
type Number_List is array (Positive range <>) of Number;
 
procedure Put (List : Number_List);
 
task type Calculate_Factors is
entry Start (The_Number : in Number);
entry Get_Size (Size : out Natural);
entry Get_Result (List : out Number_List);
end Calculate_Factors;
 
end Prime_Numbers;

prime_numbers.adb:

with Ada.Text_IO;
package body Prime_Numbers is
 
procedure Put (List : Number_List) is
begin
for Index in List'Range loop
Ada.Text_IO.Put (Image (List (Index)));
end loop;
end Put;
 
task body Calculate_Factors is
Size : Natural := 0;
N  : Number;
M  : Number;
K  : Number  := Two;
begin
accept Start (The_Number : in Number) do
N := The_Number;
M := N;
end Start;
-- Estimation of the result length from above
while M >= Two loop
M  := (M + One) / Two;
Size := Size + 1;
end loop;
M := N;
-- Filling the result with prime numbers
declare
Result : Number_List (1 .. Size);
Index  : Positive := 1;
begin
while N >= K loop -- Divisors loop
while Zero = (M mod K) loop -- While divides
Result (Index) := K;
Index  := Index + 1;
M  := M / K;
end loop;
K := K + One;
end loop;
Index := Index - 1;
accept Get_Size (Size : out Natural) do
Size := Index;
end Get_Size;
accept Get_Result (List : out Number_List) do
List (1 .. Index) := Result (1 .. Index);
end Get_Result;
end;
end Calculate_Factors;
 
end Prime_Numbers;

Example usage:

parallel.adb:

with Ada.Text_IO;
with Prime_Numbers;
procedure Parallel is
package Integer_Primes is new Prime_Numbers (
Number => Integer, -- use Large_Integer for longer numbers
Zero => 0,
One => 1,
Two => 2,
Image => Integer'Image);
 
My_List : Integer_Primes.Number_List :=
( 12757923,
12878611,
12757923,
15808973,
15780709,
197622519);
 
Decomposers : array (My_List'Range) of Integer_Primes.Calculate_Factors;
Lengths  : array (My_List'Range) of Natural;
Max_Length  : Natural := 0;
begin
for I in My_List'Range loop
-- starts the tasks
Decomposers (I).Start (My_List (I));
end loop;
for I in My_List'Range loop
-- wait until task has reached Get_Size entry
Decomposers (I).Get_Size (Lengths (I));
if Lengths (I) > Max_Length then
Max_Length := Lengths (I);
end if;
end loop;
declare
Results  :
array (My_List'Range) of Integer_Primes.Number_List (1 .. Max_Length);
Largest_Minimal_Factor : Integer := 0;
Winning_Index  : Positive;
begin
for I in My_List'Range loop
-- after Get_Result, the tasks terminate
Decomposers (I).Get_Result (Results (I));
if Results (I) (1) > Largest_Minimal_Factor then
Largest_Minimal_Factor := Results (I) (1);
Winning_Index  := I;
end if;
end loop;
Ada.Text_IO.Put_Line
("Number" & Integer'Image (My_List (Winning_Index)) &
" has largest minimal factor:");
Integer_Primes.Put (Results (Winning_Index) (1 .. Lengths (Winning_Index)));
Ada.Text_IO.New_Line;
end;
end Parallel;

Output:

Number 12878611 has largest minimal factor:
 47 101 2713

[edit] C

C code using OpenMP. Compiled with gcc -Wall -std=c99 -fopenmp, where GCC 4.2 or later is required. Note that the code finds the largest first prime factor, but does not return the factor list: it's just a matter of repeating the prime factor test, which adds clutter but does not make the code any more interesting. For that matter, the code uses the dumbest prime factoring method, and doesn't even test if the numbers can be divided by 2.

#include <stdio.h>
#include <omp.h>
 
int main()
{
int data[] = {12757923, 12878611, 12878893, 12757923, 15808973, 15780709, 197622519};
int largest, largest_factor = 0;
 
omp_set_num_threads(4);
/* "omp parallel for" turns the for loop multithreaded by making each thread
* iterating only a part of the loop variable, in this case i; variables declared
* as "shared" will be implicitly locked on access
*/

#pragma omp parallel for shared(largest_factor, largest)
for (int i = 0; i < 7; i++) {
int p, n = data[i];
 
for (p = 3; p * p <= n && n % p; p += 2);
if (p * p > n) p = n;
if (p > largest_factor) {
largest_factor = p;
largest = n;
printf("thread %d: found larger: %d of %d\n",
omp_get_thread_num(), p, n);
} else {
printf("thread %d: not larger:  %d of %d\n",
omp_get_thread_num(), p, n);
}
}
 
printf("Largest factor: %d of %d\n", largest_factor, largest);
return 0;
}
Output (YMMV regarding the order of output):
thread 1: found larger: 47 of 12878893
thread 0: not larger:   3 of 12757923
thread 0: not larger:   47 of 12878611
thread 3: not larger:   3 of 197622519
thread 2: not larger:   29 of 15808973
thread 2: not larger:   7 of 15780709
thread 1: not larger:   3 of 12757923
Largest factor: 47 of 12878893

[edit] C++

This uses C++11 features including lambda functions.

#include <iostream>
#include <iterator>
#include <vector>
#include <ppl.h> // MSVC++
#include <concurrent_vector.h> // MSVC++
 
struct Factors
{
int number;
std::vector<int> primes;
};
 
const int data[] =
{
12757923, 12878611, 12878893, 12757923, 15808973, 15780709, 197622519
};
 
int main()
{
// concurrency-safe container replaces std::vector<>
Concurrency::concurrent_vector<Factors> results;
 
// parallel algorithm replaces std::for_each()
Concurrency::parallel_for_each(std::begin(data), std::end(data), [&](int n)
{
Factors factors;
factors.number = n;
for (int f = 2; n > 1; ++f)
{
while (n % f == 0)
{
factors.primes.push_back(f);
n /= f;
}
}
results.push_back(factors); // add factorization to results
});
// end of parallel calculations
 
// find largest minimal prime factor in results
auto max = std::max_element(results.begin(), results.end(), [](const Factors &a, const Factors &b)
{
return a.primes.front() < b.primes.front();
});
 
// print number(s) and factorization
std::for_each(results.begin(), results.end(), [&](const Factors &f)
{
if (f.primes.front() == max->primes.front())
{
std::cout << f.number << " = [ ";
std::copy(f.primes.begin(), f.primes.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << "]\n";
}
});
return 0;
}

Output:

12878611 = [ 47 101 2713 ]
12878893 = [ 47 274019 ]

[edit] C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
 
private static void Main(string[] args)
{
int j = 0, m = 0;
decimal[] n = {12757923, 12878611, 12757923, 15808973, 15780709, 197622519};
var l = new List<int>[n.Length];
 
Parallel.For(0, n.Length, i => { l[i] = getPrimes(n[i]); });
 
for (int i = 0; i<n.Length; i++)
if (l[i].Min()>m)
{
m = l[i].Min();
j = i;
}
 
Console.WriteLine("Number {0} has largest minimal factor:", n[j]);
foreach (int list in l[j])
Console.Write(" "+list);
}
Number 12878611 has largest minimal factor:
 47 101 2713

[edit] Clojure

(use '[clojure.contrib.lazy-seqs :only [primes]])
 
(defn lpf [n]
[n (or (last
(for [p (take-while #(<= (* % %) n) primes)
 :when (zero? (rem n p))]
p))
1)])
 
(->> (range 2 100000)
(pmap lpf)
(apply max-key second)
println
time)

Output:

[99847 313]
"Elapsed time: 2547.53566 msecs"

[edit] D

[edit] Using Eager Parallel Map

This entry will work with the release of 2.066. The issue can currently be bypassed entirely, by compiling with -release.
ulong[] decompose(ulong n) pure nothrow {
typeof(return) result;
for (ulong i = 2; n >= i * i; i++)
for (; n % i == 0; n /= i)
result ~= i;
if (n != 1)
result ~= n;
return result;
}
 
void main() {
import std.stdio, std.algorithm, std.parallelism, std.typecons;
 
immutable ulong[] data = [
2UL^^59-1, 2UL^^59-1, 2UL^^59-1, 112_272_537_195_293UL,
115_284_584_522_153, 115_280_098_190_773,
115_797_840_077_099, 112_582_718_962_171,
112_272_537_095_293, 1_099_726_829_285_419];
 
//auto factors = taskPool.amap!(n => tuple(decompose(n), n))(data);
//static enum genPair = (ulong n) pure => tuple(decompose(n), n);
static genPair(ulong n) pure { return tuple(decompose(n), n); }
auto factors = taskPool.amap!genPair(data);
 
auto pairs = factors.map!(p => tuple(p[0].reduce!min, p[1]));
writeln("N. with largest min factor: ", pairs.reduce!max[1]);
}
Output:
N. with largest min factor: 7310027617718202995

[edit] Using Threads

import std.stdio, std.math, std.algorithm, std.typecons,
core.thread, core.stdc.time;
 
final class MinFactor: Thread {
private immutable ulong num;
private ulong[] fac;
private ulong minFac;
 
this(in ulong n) /*pure nothrow*/ {
super(&run);
num = n;
fac = new ulong[0];
}
 
@property ulong number() const pure nothrow {
return num;
}
 
@property const(ulong[]) factors() const pure nothrow {
return fac;
}
 
@property ulong minFactor() const pure nothrow {
return minFac;
}
 
private void run() {
immutable clock_t begin = clock;
switch (num) {
case 0: fac = [];
break;
 
case 1: fac = [1];
break;
 
default:
uint limit = cast(uint)(1 + double(num).sqrt);
ulong n = num;
for (ulong divi = 3; divi < limit; divi += 2) {
if (n == 1)
break;
if ((n % divi) == 0) {
while ((n > 1) && ((n % divi) == 0)) {
fac ~= divi;
n /= divi;
}
limit = cast(uint)(1 + double(n).sqrt);
}
}
if (n > 1)
fac ~= n;
}
minFac = fac.reduce!min;
immutable clock_t end = clock;
writefln("num: %20d --> min. factor: %20d ticks(%7d -> %7d)",
num, minFac, begin, end);
}
}
 
void main() {
immutable ulong[] numbers = [
2UL^^59-1, 2UL^^59-1, 2UL^^59-1, 112_272_537_195_293UL,
115_284_584_522_153, 115_280_098_190_773,
115_797_840_077_099, 112_582_718_962_171,
112_272_537_095_293, 1_099_726_829_285_419];
 
auto tGroup = new ThreadGroup;
foreach (const n; numbers)
tGroup.add(new MinFactor(n));
 
writeln("Minimum factors for respective numbers are:");
foreach (t; tGroup)
t.start;
tGroup.joinAll;
 
auto maxMin = tuple(0UL, [0UL], 0UL);
foreach (thread; tGroup) {
auto s = cast(MinFactor)thread;
if (s !is null && maxMin[2] < s.minFactor)
maxMin = tuple(s.number, s.factors.dup, s.minFactor);
}
 
writefln("Number with largest min. factor is %16d," ~
" with factors:\n\t%s", maxMin.tupleof);
}

Output (1 core CPU, edited to fit page width):

Minimum factors for respective numbers are:
num:   576460752303423487 --> min. factor: 179951  ticks(  16 ->  78)
num:   576460752303423487 --> min. factor: 179951  ticks(  78 -> 125)
num:   576460752303423487 --> min. factor: 179951  ticks( 141 -> 203)
num:      112272537195293 --> min. factor:    173  ticks( 203 -> 203)
num:      115284584522153 --> min. factor: 513937  ticks( 203 -> 219)
num:      115280098190773 --> min. factor: 513917  ticks( 219 -> 250)
num:      115797840077099 --> min. factor: 544651  ticks( 250 -> 266)
num:      112582718962171 --> min. factor:   3121  ticks( 266 -> 266)
num:      112272537095293 --> min. factor:    131  ticks( 266 -> 266)
num:     1099726829285419 --> min. factor:    271  ticks( 266 -> 266)
Number with largest min. factor is  115797840077099, with factors:
        [544651, 212609249]

[edit] Erlang

Perhaps it is of interest that the code will handle exceptions correctly. If the function (in this case factors/1) throws an exception, then the task will get it. I had to copy factors/1 from Prime_decomposition since it is only a fragment, not a complete example.

 
-module( parallel_calculations ).
 
-export( [fun_results/2, task/0] ).
 
fun_results( Fun, Datas ) ->
My_pid = erlang:self(),
Pids = [fun_spawn( Fun, X, My_pid ) || X <- Datas],
[fun_receive(X) || X <- Pids].
 
task() ->
Numbers = [12757923, 12878611, 12757923, 15808973, 15780709, 197622519],
Results = fun_results( fun factors/1, Numbers ),
Min_results = [lists:min(X) || X <- Results],
{_Max_min_factor, Number} = lists:max( lists:zip(Min_results, Numbers) ),
{Number, Factors} = lists:keyfind( Number, 1, lists:zip(Numbers, Results) ),
io:fwrite( "~p has largest minimal factor among its prime factors ~p~n", [Number, Factors] ).
 
 
 
factors(N) -> factors(N,2,[]).
 
factors(1,_,Acc) -> Acc;
factors(N,K,Acc) when N rem K == 0 -> factors(N div K,K, [K|Acc]);
factors(N,K,Acc) -> factors(N,K+1,Acc).
 
fun_receive( Pid ) ->
receive
{ok, Result, Pid} -> Result;
{Type, Error, Pid} -> erlang:Type( Error )
end.
 
fun_spawn( Fun, Data, My_pid ) ->
erlang:spawn( fun() ->
Result = try
{ok, Fun(Data), erlang:self()}
 
catch
Type:Error -> {Type, Error, erlang:self()}
 
end,
My_pid ! Result
end ).
 
Output:
8> parallel_calculations:task().
12878611 has largest minimal factor among its prime factors [2713,101,47]

[edit] Factor

[edit] Manuel Thread Management

 
USING: io kernel fry locals sequences arrays math.primes.factors math.parser channels threads prettyprint ;
IN: <filename>
 
:: map-parallel ( seq quot -- newseq )
<channel> :> ch
seq [ '[ _ quot call ch to ] "factors" spawn ] { } map-as
dup length [ ch from ] replicate nip ;
 
{ 576460752303423487 576460752303423487
576460752303423487 112272537195293
115284584522153 115280098190773
115797840077099 112582718962171
112272537095293 1099726829285419 }
dup [ factors ] map-parallel
dup [ infimum ] map dup supremum
swap index swap dupd nth -rot swap nth
"Number with largest min. factor is " swap number>string append
", with factors: " append write .
 

Output:

Number with largest min. factor is 1099726829285419, with factors: { 544651 212609249 }

[edit] With Concurency Module

 
USING: kernel io prettyprint sequences arrays math.primes.factors math.parser concurrency.combinators ;
{ 576460752303423487 576460752303423487 576460752303423487 112272537195293
115284584522153 115280098190773 115797840077099 112582718962171 }
dup [ factors ] parallel-map dup [ infimum ] map dup supremum
swap index swap dupd nth -rot swap nth
"Number with largest min. factor is " swap number>string append
", with factors: " append write .
 

Output:

Number with largest min. factor is 115797840077099, with factors: { 544651 212609249 }

[edit] F#

open System
open PrimeDecomp // Has the decompose function from the Prime decomposition task
 
let data = [112272537195293L; 112582718962171L; 112272537095293L; 115280098190773L; 115797840077099L; 1099726829285419L]
let decomp num = decompose num 2L
 
let largestMinPrimeFactor (numbers: int64 list) =
let decompDetails = Async.Parallel [ for n in numbers -> async { return n, decomp n } ] // Compute the number and its prime decomposition list
|> Async.RunSynchronously // Start and wait for all parallel computations to complete.
|> Array.sortBy (snd >> List.min >> (~-)) // Sort in descending order, based on the min prime decomp number.
 
decompDetails.[0]
 
let showLargestMinPrimeFactor numbers =
let number, primeList = largestMinPrimeFactor numbers
printf "Number %d has largest minimal factor:\n " number
List.iter (printf "%d ") primeList
 
showLargestMinPrimeFactor data

Output:

Number 115797840077099 has largest minimal factor:
    544651 212609249

[edit] Go

package main
 
import (
"fmt"
"math/big"
)
 
// collection of numbers. A slice is used for the collection.
// The elements are big integers, since that's what the function Primes
// uses (as was specified by the Prime decomposition task.)
var numbers = []*big.Int{
big.NewInt(12757923),
big.NewInt(12878611),
big.NewInt(12878893),
big.NewInt(12757923),
big.NewInt(15808973),
big.NewInt(15780709),
}
 
// main just calls the function specified by the task description and
// prints results. note it allows for multiple numbers with the largest
// minimal factor. the task didn't specify to handle this, but obviously
// it's possible.
func main() {
rs := lmf(numbers)
fmt.Println("largest minimal factor:", rs[0].decomp[0])
for _, r := range rs {
fmt.Println(r.number, "->", r.decomp)
}
}
 
// this type associates a number with it's prime decomposition.
// the type is neccessary so that they can be sent together over
// a Go channel, but it turns out to be convenient as well for
// the return type of lmf.
type result struct {
number *big.Int
decomp []*big.Int
}
 
// the function specified by the task description, "largest minimal factor."
func lmf([]*big.Int) []result {
// construct result channel and start a goroutine to decompose each number.
// goroutines run in parallel as CPU cores are available.
rCh := make(chan result)
for _, n := range numbers {
go decomp(n, rCh)
}
 
// collect results. <-rCh returns a single result from the result channel.
// we know how many results to expect so code here collects exactly that
// many results, and accumulates a list of those with the largest
// minimal factor.
rs := []result{<-rCh}
for i := 1; i < len(numbers); i++ {
switch r := <-rCh; r.decomp[0].Cmp(rs[0].decomp[0]) {
case 1:
rs = rs[:1]
rs[0] = r
case 0:
rs = append(rs, r)
}
}
return rs
}
 
// decomp is the function run as a goroutine. multiple instances of this
// function will run concurrently, one for each number being decomposed.
// it acts as a driver for Primes, calling Primes as needed, packaging
// the result, and sending the packaged result on the channel.
// "as needed" turns out to mean sending Primes a copy of n, as Primes
// as written is destructive on its argument.
func decomp(n *big.Int, rCh chan result) {
rCh <- result{n, Primes(new(big.Int).Set(n))}
}
 
// code below copied from Prime decomposition task
var (
ZERO = big.NewInt(0)
ONE = big.NewInt(1)
)
 
func Primes(n *big.Int) []*big.Int {
res := []*big.Int{}
mod, div := new(big.Int), new(big.Int)
for i := big.NewInt(2); i.Cmp(n) != 1; {
div.DivMod(n, i, mod)
for mod.Cmp(ZERO) == 0 {
res = append(res, new(big.Int).Set(i))
n.Set(div)
div.DivMod(n, i, mod)
}
i.Add(i, ONE)
}
return res
}

Output:

largest minimal factor: 47
12878611 -> [47 101 2713]
12878893 -> [47 274019]

[edit] Haskell

import Control.Parallel.Strategies
import Control.DeepSeq
import Data.List
import Data.Function
 
nums :: [Integer]
nums = [112272537195293
,112582718962171
,112272537095293
,115280098190773
,115797840077099
,1099726829285419]
 
lowestFactor :: Integral a => a -> a -> a
lowestFactor s n | n `rem` 2 == 0 = 2
| otherwise = head $ y
where y = [x | x <- [s..ceiling . sqrt $ fromIntegral n]
++ [n], n `rem` x == 0, x `rem` 2 /= 0]
 
primeFactors l n = f n l []
where f n l xs = if n > 1 then f (n `div` l) (lowestFactor (max l 3) (n `div` l)) (l:xs)
else xs
 
minPrimes ns = (\(x,y) -> (x,primeFactors y x)) $
maximumBy (compare `on` snd) $
zip ns (parMap rdeepseq (lowestFactor 3) ns)
 
main :: IO ()
main = do
print $ minPrimes nums
 

Output

(115797840077099,[212609249,544651])

[edit] Icon and Unicon

The following only works in Unicon.

procedure main(A)
threads := []
L := list(*A)
every i := 1 to *A do put(threads, thread L[i] := primedecomp(A[i]))
every wait(!threads)
 
maxminF := L[maxminI := 1][1]
every i := 2 to *L do if maxminF <:= L[i][1] then maxminI := i
every writes((A[maxminI]||": ")|(!L[maxminI]||" ")|"\n")
end
 
procedure primedecomp(n) #: return a list of factors
every put(F := [], genfactors(n))
return F
end
 
link factors
 

Sample run:

->pc 57646075230343 112272537195 115284584525
57646075230343: 8731 6602459653 
->

[edit] J

The code at [1] implements parallel computation. With it, we can write

   numbers =. 12757923 12878611 12878893 12757923 15808973 15780709 197622519
factors =. q:&.> parallelize 2 numbers NB. q: is parallelized here
ind =. (i. >./) <./@> factors
ind { numbers ;"_1 factors
┌────────┬───────────┐
1287861147 101 2713
└────────┴───────────┘

[edit] JavaScript

This code demonstrates Web Workers. This should work on current versions of Firefox, Safari, Chrome and Opera.

This first portion should be placed in a file called "parallel_worker.js". This file contains the logic used by every worker created.

 
var onmessage = function(event) {
postMessage({"n" : event.data.n,
"factors" : factor(event.data.n),
"id" : event.data.id});
};
 
function factor(n) {
var factors = [];
for(p = 2; p <= n; p++) {
if((n % p) == 0) {
factors[factors.length] = p;
n /= p;
}
}
return factors;
}
 

For each number a worker is spawned. Once the final worker completes its task (worker_count is reduced to 0), the reduce function is called to determine which number is the answer.

 
var numbers = [12757923, 12878611, 12757923, 15808973, 15780709, 197622519];
var workers = [];
var worker_count = 0;
 
var results = [];
 
for(var i = 0; i < numbers.length; i++) {
worker_count++;
workers[i] = new Worker("parallel_worker.js");
workers[i].onmessage = accumulate;
workers[i].postMessage({n: numbers[i], id: i});
}
 
function accumulate(event) {
n = event.data.n;
factors = event.data.factors;
id = event.data.id;
console.log(n + " : " + factors);
results[id] = {n:n, factors:factors};
// Cleanup - kill the worker and countdown until all work is done
workers[id].terminate();
worker_count--;
if(worker_count == 0)
reduce();
}
 
function reduce() {
answer = 0;
for(i = 1; i < results.length; i++) {
min = results[i].factors[0];
largest_min = results[answer].factors[0];
if(min > largest_min)
answer = i;
}
n = results[answer].n;
factors = results[answer].factors;
console.log("The number with the relatively largest factors is: " + n + " : " + factors);
}
 

[edit] Mathematica

 
hasSmallestFactor[data_List]:=Sort[Transpose[{ParallelTable[FactorInteger[x][[1, 1]], {x, data}],data}]][[1, 2]]

[edit] PARI/GP

See Bill Allombert's slides on parallel programming in GP. This can be configured to use either MPI (good for many networked computers) or pthreads (good for a single machine).

Works with: PARI/GP version 2.6 with bill-pareval branch
v=pareval(vector(1000,i,()->factor(2^i+1)[1,1]));
vecmin(v)

[edit] OxygenBasic

 
'CONFIGURATION
'=============
 
% max 8192 'Maximum amount of Prime Numbers (must be 2^n) (excluding 1 and 2)
% cores 4 'CPU cores available (limited to 4 here)
% share 2048 'Amount of numbers allocated to each core
 
'SETUP
'=====
 
'SOURCE DATA BUFFERS
 
sys primes[max]
sys numbers[max]
 
'RESULT BUFFER
 
double pp[max] 'main thread
 
 
'MULTITHREADING AND TIMING API
'=============================
 
extern lib "kernel32.dll"
'
void QueryPerformanceCounter(quad*c)
void QueryPerformanceFrequency(quad*freq)
sys CreateThread (sys lpThreadAttributes, dwStackSize, lpStartAddress, lpParameter, dwCreationFlags, *lpThreadId)
dword WaitForMultipleObjects(sys nCount,*lpHandles, bWaitAll, dwMilliseconds)
bool CloseHandle(sys hObject)
void Sleep(sys dwMilliSeconds)
'
quad freq,t1,t2
QueryPerformanceFrequency freq
 
 
'MACROS AND FUNCTIONS
'====================
 
 
macro FindPrimes(p)
'==================
finit
sys n=1
sys c,k
do
n+=2
if c>=max then exit do
'
'IS IT DIVISIBLE BE ANY PREVIOUS PRIME
'
for k=1 to c
if frac(n/p[k])=0 then exit for
next
'
if k>c then
c++
p[c]=n 'STORE PRIME
end if
end do
end macro
 
 
macro ProcessNumbers(p,bb)
'=========================
finit
sys i,b,e
b=bb*share
e=b+share
sys v,w
for i=b+1 to e
v=numbers(i)
for j=max to 1 step -1
w=primes(j)
if w<v then
if frac(v/w)=0 then
p(i)=primes(j) 'store highest factor
exit for 'process next number
end if
end if
next
next
end macro
 
'THREAD FUNCTIONS
 
function threadA(sys v) as sys
ProcessNumbers(pp,v)
end function
 
 
function threadB(sys v) as sys
ProcessNumbers(pp,v)
end function
 
 
function threadC(sys v) as sys
ProcessNumbers(pp,v)
end function
 
 
end extern
 
function mainThread(sys b)
'===========================
ProcessNumbers(pp,b)
end function
 
 
'SOURCE DATA GENERATION
 
sys seed = 0x12345678
 
function Rnd() as sys
'====================
'
mov eax,seed
rol eax,7
imul eax,eax,13
mov seed,eax
return eax
end function
 
 
function GenerateNumbers()
'=========================
sys i,v,mask
mask=max * 8 -1 'as bit mask
for i=1 to max
v=rnd()
v and=mask
numbers(i)=v
next
end function
 
 
 
FindPrimes(primes)
 
GenerateNumbers()
 
 
 
% threads Cores-1
 
% INFINITE 0xFFFFFFFF 'Infinite timeout
 
sys Funs[threads]={@threadA,@threadB,@threadC} '3 additional threads
sys hThread[threads], id[threads], i
'
'START TIMER
'
QueryPerformanceCounter t1
'
for i=1 to threads
hThread(i) = CreateThread 0,0,funs(i),i,0,id(i)
next
 
 
MainThread(0) 'process numbers in main thread (bottom share)
 
if threads>0 then
WaitForMultipleObjects Threads, hThread, 1, INFINITE
end if
 
for i=1 to Threads
CloseHandle hThread(i)
next
 
'CAPTURE NUMBER WITH HIGHEST PRIME FACTOR
 
sys n,f
for i=1 to max
if pp(i)>f then f=pp(i) : n=i
next
 
'STOP TIMER
 
QueryPerformanceCounter t2
 
print str((t2-t1)/freq,3) " secs " numbers(n) " " f 'number with highest prime factor
 

[edit] Perl 6

Assuming that factors is defined exactly as in the prime decomposition task:

my @nums = 12757923, 12878611, 123456789, 15808973, 15780709, 197622519;
 
my @factories;
@factories[$_] := factors(@nums[$_]) for ^@nums;
my $gmf = ([max] @factories»[0] »=>« @nums).value;
 

The line with the for loop is just setting up a bunch of lazy lists, one for each number to be factored, but doesn't actually do any of the work of factoring. Most of the parallelizing work is done by the hyperoperators that demand the first value from each of the factories' lists, then builds (again in parallel) the pairs associating each first value with its original value. The [max] reduction finds the pair with the largest key, from which we can easily extract the greatest minimum factor candidate, and then refactor it completely.

The rakudo system does not actually do hypers in parallel yet, but when it does, this can automatically parallelize. (Hypers do parallelize in pugs, but it doesn't do some of the other things we rely on here.) It will be up to each individual compiler to determine how many cores to use for any given hyperoperator; the construct merely promises the compiler that it can be parallelized, but does not require that it must be.

There is also some pipelining that can happen within the factors routine itself, which uses a gather/take construct, which the compiler may implement using either coroutines or threads as it sees fit. Threading pipelines can make more sense on, say, a cell architecture.

[edit] PicoLisp

The 'later' function is used in PicoLisp to start parallel computations. The following solution calls 'later' on the 'factor' function from Prime decomposition#PicoLisp, and then 'wait's until all results are available:

(let Lst
(mapcan
'((N)
(later (cons) # When done,
(cons N (factor N)) ) ) # return the number and its factors
(quote
188573867500151328137405845301 # Process a collection of 12 numbers
3326500147448018653351160281
979950537738920439376739947
2297143294659738998811251
136725986940237175592672413
3922278474227311428906119
839038954347805828784081
42834604813424961061749793
2651919914968647665159621
967022047408233232418982157
2532817738450130259664889
122811709478644363796375689 ) )
(wait NIL (full Lst)) # Wait until all computations are done
(maxi '((L) (apply min L)) Lst) ) # Result: Number in CAR, factors in CDR

Output:

-> (2532817738450130259664889 6531761 146889539 2639871491)

[edit] Prolog

Works with: swipl

This piece needs prime_decomp definition from the Prime decomposition#Prolog example, it worked on my swipl, but I don't know how other Dialects thread.

threaded_decomp(Number,ID):-
thread_create(
(prime_decomp(Number,Y),
thread_exit((Number,Y)))
,ID,[]).
 
threaded_decomp_list(List,Erg):-
maplist(threaded_decomp,List,IDs),
maplist(thread_join,IDs,Results),
maplist(pack_exit_out,Results,Smallest_Factors_List),
largest_min_factor(Smallest_Factors_List,Erg).
 
pack_exit_out(exited(X),X).
%Note that here some error handling should happen.
 
largest_min_factor([(N,Facs)|A],(N2,Fs2)):-
min_list(Facs,MF),
largest_min_factor(A,(N,MF,Facs),(N2,_,Fs2)).
 
largest_min_factor([],Acc,Acc).
largest_min_factor([(N1,Facs1)|Rest],(N2,MF2,Facs2),Goal):-
min_list(Facs1, MF1),
(MF1 > MF2->
largest_min_factor(Rest,(N1,MF1,Facs1),Goal);
largest_min_factor(Rest,(N2,MF2,Facs2),Goal)).
 
 
format_it(List):-
threaded_decomp_list(List,(Number,Factors)),
format('Number with largest minimal Factor is ~w\nFactors are ~w\n',
[Number,Factors]).
 

Example (Numbers Same as in Ada Example):

?- ['prime_decomp.prolog', parallel].
% prime_decomp.prolog compiled 0.00 sec, 3,392 bytes
% parallel compiled 0.00 sec, 4,672 bytes
true.
format_it([12757923,
       12878611, 
       12757923, 
       15808973, 
       15780709, 
      197622519]).
Number with largest minimal factor is 12878611
Factors are [2713, 101, 47]
true.

[edit] PureBasic

Structure IO_block
ThreadID.i
StartSeamaphore.i
Value.q
MinimumFactor.i
List Factors.i()
EndStructure
;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
 
Declare Factorize(*IO.IO_block)
Declare main()
;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
 
Main()
End
;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
 
Procedure Main()
Protected AvailableCpu, MainSemaphore
Protected i, j, qData.q, Title$, Message$
NewList T.IO_block()
;
AvailableCpu = Val(GetEnvironmentVariable("NUMBER_OF_PROCESSORS"))
If AvailableCpu<1: AvailableCpu=1: EndIf
MainSemaphore = CreateSemaphore(AvailableCpu)
;
Restore Start_of_data
For i=1 To (?end_of_data-?Start_of_data) / SizeOf(Quad)
; Start all threads at ones, they will then be let to
; self-oganize according to the availiable Cores.
AddElement(T())
Read.q qData
T()\Value = qData
T()\StartSeamaphore = MainSemaphore
T()\ThreadID = CreateThread(@Factorize(), @T())
Next
;
ForEach T()
; Wait for all threads to complete their work and
; find the smallest factor from eact task.
WaitThread(T()\ThreadID)
Next
;
i = OffsetOf(IO_block\MinimumFactor)
SortStructuredList(T(), #PB_Sort_Integer, i, #PB_Sort_Descending)
FirstElement(T())
Title$="Info"
Message$="Number "+Str(T()\Value)+" has largest minimal factor:"+#CRLF$
ForEach T()\Factors()
Message$ + Str(T()\Factors())+" "
Next
MessageRequester(Title$, Message$)
EndProcedure
 
ProcedureDLL Factorize(*IO.IO_block) ; Fill list Factors() with the factor parts of Number
;Based on http://rosettacode.org/wiki/Prime_decomposition#PureBasic
With *IO
Protected Value.q=\Value
WaitSemaphore(\StartSeamaphore)
Protected I = 3
ClearList(\Factors())
While Value % 2 = 0
AddElement(\Factors())
\Factors() = 2
Value / 2
Wend
Protected Max = Value
While I <= Max And Value > 1
While Value % I = 0
AddElement(\Factors())
\Factors() = I
Value / I
Wend
I + 2
Wend
SortList(\Factors(), #PB_Sort_Ascending)
FirstElement(\Factors())
\MinimumFactor=\Factors()
SignalSemaphore(\StartSeamaphore)
EndWith ;*IO
EndProcedure
 
DataSection
Start_of_data: ; Same numbers as Ada
Data.q 12757923, 12878611, 12757923, 15808973, 15780709, 197622519
end_of_data:
EndDataSection
 

PB Parallel Calculations.png

[edit] Python

[edit] Python3 - concurrent

Python 3.2 has a new concurrent.futures module that allows for the easy specification of thread-parallel or process-parallel processes. The following is modified from their example and will run, by default, with as many processes as there are available cores on your machine.

Note that there is no need to calculate all prime factors of all NUMBERS when only the prime factors of the number with the lowest overall prime factor is needed.

from concurrent import futures
from math import floor, sqrt
 
NUMBERS = [
112272537195293,
112582718962171,
112272537095293,
115280098190773,
115797840077099,
1099726829285419]
# NUMBERS = [33, 44, 55, 275]
 
def lowest_factor(n, _start=3):
if n % 2 == 0:
return 2
search_max = int(floor(sqrt(n))) + 1
for i in range(_start, search_max, 2):
if n % i == 0:
return i
return n
 
def prime_factors(n, lowest):
pf = []
while n > 1:
pf.append(lowest)
n //= lowest
lowest = lowest_factor(n, max(lowest, 3))
return pf
 
def prime_factors_of_number_with_lowest_prime_factor(NUMBERS):
with futures.ProcessPoolExecutor() as executor:
low_factor, number = max( (l, f) for l, f in zip(executor.map(lowest_factor, NUMBERS), NUMBERS) )
all_factors = prime_factors(number, low_factor)
return number, all_factors
 
 
def main():
print('For these numbers:')
print('\n '.join(str(p) for p in NUMBERS))
number, all_factors = prime_factors_of_number_with_lowest_prime_factor(NUMBERS)
print(' The one with the largest minimum prime factor is {}:'.format(number))
print(' All its prime factors in order are: {}'.format(all_factors))
 
if __name__ == '__main__':
main()

Sample Output

For these numbers:
  112272537195293
  112582718962171
  112272537095293
  115280098190773
  115797840077099
  1099726829285419
    The one with the largest minimum prime factor is 115797840077099:
      All its prime factors in order are: [544651, 212609249]


[edit] Python General - multiprocessing

This method works for both Python2 and Python3 using the standard library module multiprocessing. The result of the following code is the same as the previous example only the different package is used.

import multiprocessing
 
# ========== #Python3 - concurrent
from math import floor, sqrt
 
numbers = [
112272537195293,
112582718962171,
112272537095293,
115280098190773,
115797840077099,
1099726829285419]
# numbers = [33, 44, 55, 275]
 
def lowest_factor(n, _start=3):
if n % 2 == 0:
return 2
search_max = int(floor(sqrt(n))) + 1
for i in range(_start, search_max, 2):
if n % i == 0:
return i
return n
 
def prime_factors(n, lowest):
pf = []
while n > 1:
pf.append(lowest)
n //= lowest
lowest = lowest_factor(n, max(lowest, 3))
return pf
# ========== #Python3 - concurrent
 
def prime_factors_of_number_with_lowest_prime_factor(numbers):
pool = multiprocessing.Pool(processes=5)
factors = pool.map(lowest_factor,numbers)
 
low_factor,number = max((l,f) for l,f in zip(factors,numbers))
all_factors = prime_factors(number,low_factor)
return number,all_factors
 
if __name__ == '__main__':
print('For these numbers:')
print('\n '.join(str(p) for p in numbers))
number, all_factors = prime_factors_of_number_with_lowest_prime_factor(numbers)
print(' The one with the largest minimum prime factor is {}:'.format(number))
print(' All its prime factors in order are: {}'.format(all_factors))
 

[edit] Racket

 
#lang racket
(require math)
(provide main)
 
(define (smallest-factor n)
(list (first (first (factorize n))) n))
 
(define numbers
'(112272537195293 112582718962171 112272537095293
115280098190773 115797840077099 1099726829285419))
 
(define (main)
 ; create as many instances of Racket as
 ; there are numbers:
(define ps
(for/list ([_ numbers])
(place ch
(place-channel-put
ch
(smallest-factor
(place-channel-get ch))))))
 ; send the numbers to the instances:
(map place-channel-put ps numbers)
 ; get the results and find the maximum:
(argmax first (map place-channel-get ps)))
 

Session:

 
> (main)
'(544651 115797840077099)
 

[edit] Tcl

With Tcl, it is necessary to explicitly perform computations in other threads because each thread is strongly isolated from the others (except for inter-thread messaging). However, it is entirely practical to wrap up the communications so that only a small part of the code needs to know very much about it, and in fact most of the complexity is managed by a thread pool; each value to process becomes a work item to be handled. It is easier to transfer the results by direct messaging instead of collecting the thread pool results, since we can leverage Tcl's vwait command nicely.

Works with: Tcl version 8.6
package require Tcl 8.6
package require Thread
 
# Pooled computation engine; runs event loop internally
namespace eval pooled {
variable poolSize 3; # Needs to be tuned to system size
 
proc computation {computationDefinition entryPoint values} {
variable result
variable poolSize
# Add communication shim
append computationDefinition [subst -nocommands {
proc poolcompute {value target} {
set outcome [$entryPoint \$value]
set msg [list set ::pooled::result(\$value) \$outcome]
thread::send -async \$target \$msg
}
}]
 
# Set up the pool
set pool [tpool::create -initcmd $computationDefinition \
-maxworkers $poolSize]
 
# Prepare to receive results
unset -nocomplain result
array set result {}
 
# Dispatch the computations
foreach value $values {
tpool::post $pool [list poolcompute $value [thread::id]]
}
 
# Wait for results
while {[array size result] < [llength $values]} {vwait pooled::result}
 
# Dispose of the pool
tpool::release $pool
 
# Return the results
return [array get result]
}
}

This is the definition of the prime factorization engine (a somewhat stripped-down version of the Tcl Prime decomposition solution:

# Code for computing the prime factors of a number
set computationCode {
namespace eval prime {
variable primes [list 2 3 5 7 11]
proc restart {} {
variable index -1
variable primes
variable current [lindex $primes end]
}
 
proc get_next_prime {} {
variable primes
variable index
if {$index < [llength $primes]-1} {
return [lindex $primes [incr index]]
}
variable current
while 1 {
incr current 2
set p 1
foreach prime $primes {
if {$current % $prime} {} else {
set p 0
break
}
}
if {$p} {
return [lindex [lappend primes $current] [incr index]]
}
}
}
 
proc factors {num} {
restart
set factors [dict create]
for {set i [get_next_prime]} {$i <= $num} {} {
if {$num % $i == 0} {
dict incr factors $i
set num [expr {$num / $i}]
continue
} elseif {$i*$i > $num} {
dict incr factors $num
break
} else {
set i [get_next_prime]
}
}
return $factors
}
}
}
 
# The values to be factored
set values {
188573867500151328137405845301
3326500147448018653351160281
979950537738920439376739947
2297143294659738998811251
136725986940237175592672413
3922278474227311428906119
839038954347805828784081
42834604813424961061749793
2651919914968647665159621
967022047408233232418982157
2532817738450130259664889
122811709478644363796375689
}

Putting everything together:

# Do the computation, getting back a dictionary that maps
# values to its results (itself an ordered dictionary)
set results [pooled::computation $computationCode prime::factors $values]
 
# Find the maximum minimum factor with sorting magic
set best [lindex [lsort -integer -stride 2 -index {1 0} $results] end-1]
 
# Print in human-readable form
proc renderFactors {factorDict} {
dict for {factor times} $factorDict {
lappend v {*}[lrepeat $times $factor]
}
return [join $v "*"]
}
puts "$best = [renderFactors [dict get $results $best]]"
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox