[erlang-questions] Generating Primes and the O'Neill paper
Angel Alvarez
clist@REDACTED
Wed Dec 16 23:29:43 CET 2009
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]).
More information about the erlang-questions
mailing list