[erlang-questions] Generating Primes and the O'Neill paper

[Angel Alvarez]

Opps !!  15 is not prime is'nt it?

Ive include an improved version...

compare(X,Y) ->
	case X == Y of
		true -> 
			equal;
		false -> 
			case X > Y of
				true -> 
					greater;
				false ->
					smaller
			end
	end.

is there a better way of writing this test?

/Angel


El Miércoles, 16 de Diciembre de 2009 Angel Alvarez escribió:
> El Miércoles, 16 de Diciembre de 2009 James Aimonetti escribió:
> > I have been working the Project Euler problems and wanted to see what 
> > the list thought about my implementation of a prime number generator 
> > that is based off the Melissa O'Neill paper[1]. I also used a lazy list 
> > idea from one of Joe Armstrong's suggestions[2] concerning a Euler 
> > problem. My implementation uses the priority queue (page 7 of the PDF), 
> > and I'm using a skew heap I found[3] on this list to accomplish that, 
> > which I modified to handle key-value pairs instead of just keys.
> > 
> > I made a pastie[4] to view the code.
> > 
> > I tried to stay true to the Haskell version in the paper but had to 
> > modify some parts. I don't know Haskell so I easily could have lost 
> > something in the translation.
> > 
> > Oh, the function is called queue because I was playing with other 
> > methods, like the unfaithful sieve, but I've only included the queue/1 
> > in the pastie. I am going to try the wheel and other optimizations 
> > talked about in the paper, but wanted a sanity check from the gurus that 
> > my Erlang is decent and the implementation isn't totally bunk.
> > 
> > Thanks in advance for any advice or corrections.
> > 
> > [1] - http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
> > [2] - http://www.erlang.org/cgi-bin/ezmlm-cgi?4:mss:177:khdaceipfabbicmifdhf
> > [3] - 
> > http://www.erlang.org/pipermail/erlang-questions/2007-August/028769.html
> > [4] - http://pastie.org/746050
> > 
> Hi this paper is very interesting, but being novice icant hardly say you 
> something about your code. Maybe you can check mine for a 
> multiprocess approach.
> 
> Ive include my try on this "genuine" erathostenes sieve.
> 
> every worker stores one prime and properly crosses off on the fly when the numbers
> are testet. Its a kind of lazy as it creates new worker in demand...
> 
> With my code you can do a naive exercise:
> 
> sinosuke@REDACTED:~/Documents/Personal/Erlang/Code/primality> erlc multi_erathostenes.erl
> sinosuke@REDACTED:~/Documents/Personal/Erlang/Code/primality> erl
> Erlang R13B01 (erts-5.7.2) [source] [rq:1] [async-threads:0] [hipe] [kernel-poll:false]
> 
> Eshell V5.7.2  (abort with ^G)
> 
> 1> OnePID=spawn(multi_erathostenes,worker,[2,4]).
> <0.35.0>
> 2> [ OnePID ! {test,X} || X <- [3,4,5,6,7,8,9,10,11]].
> 
> [Worker of prime: 2 (4)] Spawn new worker for Prime: 3
> [Worker of prime: 2 (4)] Found composite: 4
> [Worker of prime: 2 (6)] passing along: 5
> [Worker of prime: 2 (6)] Found composite: 6
> [Worker of prime: 3 (9)] Spawn new worker for Prime: 5
> [Worker of prime: 2 (8)] passing along: 7
> [Worker of prime: 2 (8)] Found composite: 8
> [Worker of prime: 3 (9)] passing along: 7
> [Worker of prime: 2 (10)] passing along: 9
> [Worker of prime: 5 (25)] Spawn new worker for Prime: 7
> [Worker of prime: 2 (10)] Found composite: 10
> [Worker of prime: 3 (9)] Found composite: 9
> [Worker of prime: 2 (12)] passing along: 11
> [Worker of prime: 3 (12)] passing along: 11
> [Worker of prime: 5 (25)] passing along: 11
> [Worker of prime: 7 (49)] Spawn new worker for Prime: 11
> 
> 
> /Angel



-- 
No imprima este correo si no es necesario. El medio ambiente está en nuestras manos.
->>-----------------------------------------------
    Clist UAH a.k.a Angel
---------------------------------[www.uah.es]-<<--

Tú lo compras, yo lo copio. Todo legal.
-------------- next part --------------
% Multi "Genuine" Erathostenes

%         02    03    05    07    11    13    17
% P 02 -> 04
% P 03    04 -> 09
% C 04 == 04    09
% P 05    06    09 -> 25
% C 06 == 06    09    25
% P 07    08    09    25 -> 49
% C 08 == 08    09    25    49
% C 09    10 == 09    25    49
% C 10 == 10    12    25    49
% P 11    12    12    25    49 -> 121
% C 12 == 12    12    25    49    121
% P 13    14    15    25    49    121 -> 169
% C 14 == 14    15    25    49    121    169
% C 15    16 == 15    25    49    121    169
% C 16 == 16    18    25    49    121    169
% P 17    18    18    25    49    121    169 -> 289

-module(multi_erathostenes).
-compile(export_all).

compare(X,Y) ->
	case X == Y of
		true -> 
			equal;
		false -> 
			case X > Y of
				true -> 
					greater;
				false ->
					smaller
			end
	end.

worker(Prime,UpperBound)->
	receive
		{test,Number} ->
			case compare(Number,UpperBound) of
				equal ->
					io:format("[Worker of prime: ~w (~w)] Found composite: ~w~n",[Prime,UpperBound,Number]),
					worker(Prime,UpperBound + Prime);
				smaller ->
					io:format("[Worker of prime: ~w (~w)] Spawn new worker for Prime: ~w~n",[Prime,UpperBound,Number]),
					NextPID =spawn(?MODULE,worker,[Number,Number*Number]),
					worker(Prime,UpperBound,NextPID)
			end
	end.

worker(Prime,UpperBound,NextPID) ->
	receive
		{test,Number} ->
			case compare(Number,UpperBound) of
				equal ->
					io:format("[Worker of prime: ~w (~w)] Found composite: ~w~n",[Prime,UpperBound,Number]),
					worker(Prime,UpperBound + Prime,NextPID);
				smaller ->
					io:format("[Worker of prime: ~w (~w)] passing along: ~w~n",[Prime,UpperBound,Number]),
					NextPID ! {test,Number}, 
					worker(Prime,UpperBound,NextPID);
				greater ->
					io:format("[Worker of prime: ~w (~w)] passing along: ~w~n",[Prime,UpperBound,Number]),
					NextPID ! {test,Number}, 
					worker(Prime,UpperBound+Prime,NextPID)
			end
	end.

% main(LimiteSuperior) ->
% FirstWorkerPID = spawn(?MODULE, worker,[2,4]),
% PID_Generador = spawn(?MODULE, generador_inicial, [LimiteSuperior,self()]),
% PID_Worker = pool:pspawn(?MODULE, worker,[1,PID_Acumulador,?MAXPRIMES,[] ]),
% T1 = erlang:now(),
% Alimentador_PID = spawn(?MODULE, alimentador,[PID_Generador,PID_Worker]),
% PID_Generador ! done,
% receive 
% {primes,Numero,Lista} ->
%     io:format("[Main] Parando proceso [Acumulador]!~n"),
% 	    PID_Acumulador ! done 
% end,
% Total = lists:foldl( fun(X,Acc) -> Acc + X end,0,Lista),
% T2 = erlang:now(),
% T = timer:now_diff(T2,T1),
% io:format("[Main] Calcular la suma de los ~w primos hasta ~w : ~w ~n ha tomado ~w microsegundos~n",[Numero,LimiteSuperior,Total,T]).