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

[Angel Alvarez]

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
-- 
Agua para todo? No, Agua para Todos.
->>-----------------------------------------------
    Clist UAH a.k.a Angel
---------------------------------[www.uah.es]-<<--

-------------- 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).

worker(Prime,UpperBound)->
	receive
		{test,Number} ->
			case Number == UpperBound of
				true ->
					io:format("[Worker of prime: ~w (~w)] Found composite: ~w~n",[Prime,UpperBound,Number]),
					worker(Prime,UpperBound + Prime);
				false ->
					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 Number == UpperBound of
				true ->
					io:format("[Worker of prime: ~w (~w)] Found composite: ~w~n",[Prime,UpperBound,Number]),
					worker(Prime,UpperBound + Prime,NextPID);
				false ->
					io:format("[Worker of prime: ~w (~w)] passing along: ~w~n",[Prime,UpperBound,Number]),
					NextPID ! {test,Number}, 
					worker(Prime,UpperBound,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]).