Concurrent Prime Generator

Question

I'm going through the problems on projecteuler.net to learn how to program in Erlang, and I am having the hardest time creating a prime generator that can create all of the primes below 2 million, in less than a minute. Using the sequential style, I have already written three types of generators, including the Sieve of Eratosthenes, and none of them perform well enough.

I figured a concurrent Sieve would work great, but I'm getting bad_arity messages, and I'm not sure why. Any suggestions on why I have the problem, or how to code it properly?

Here's my code, the commented out sections are where I tried to make things concurrent:

-module(primeserver).
-compile(export_all).

start() ->
    register(primes, spawn(fun() -> loop() end)).

is_prime(N) -> rpc({is_prime,N}).

rpc(Request) ->
    primes ! {self(), Request},
    receive
        {primes, Response} ->
            Response
    end.

loop() ->
    receive
        {From, {is_prime, N}} ->
            if
                N  From ! {primes, false};
                N =:= 2 -> From ! {primes, true};
                N rem 2 =:= 0 -> From ! {primes, false};
                true ->
                    Values = is_not_prime(N),
                    Val = not(lists:member(true, Values)),
                    From ! {primes, Val}
            end,
            loop()
    end.

for(N,N,_,F) -> [F(N)];
for(I,N,S,F) when I + S  [F(I)|for(I+S, N, S, F)];
for(I,N,S,F) when I + S =:= N -> [F(I)|for(I+S, N, S, F)];
for(I,N,S,F) when I + S > N -> [F(I)].

get_list(I, Limit) ->
    if
        I 
            [I*A || A 
            []
    end.

is_not_prime(N) ->
    for(3, N, 2, 
        fun(I) -> 
            List = get_list(I,trunc(N/I)),
            lists:member(N,lists:flatten(List))
        end
        ).

    %%L = for(1,N, fun() -> spawn(fun(I) -> wait(I,N) end) end),
    %%SeedList = [A || A  
    %%      lists:foreach(fun(X) ->
    %%              Pid ! {in_list, X} 
    %%                end, SeedList)
    %%        end, L).

%%wait(I,N) ->
%%  List = [I*A || A  lists:member(X,List)
%%  end.

Answer 1

Primes parallel algorithm : http://www.cs.cmu.edu/~scandal/cacm/node8.html

Answer 2

I love Project Euler.

On the subject of prime generators, I am a big fan of the Sieve of Eratosthenes.

For the purposes of the numbers under 2,000,000 you might try a simple isPrime check implementation. I don't know how you'd do it in erlang, but the logic is simple.

For Each NUMBER in LIST_OF_PRIMES
     If TEST_VALUE % NUMBER == 0
          Then FALSE
END
TRUE

if isPrime == TRUE add TEST_VALUE to your LIST_OF_PRIMES

iterate starting at 14 or so with a preset list of your beginning primes. 

c# ran a list like this for 2,000,000 in well under the 1 minute mark

Edit: On a side note, the sieve of Eratosthenes can be implemented easily and runs quickly, but gets unwieldy when you start getting into huge lists. The simplest implementation, using a boolean array and int values runs extremely quickly. The trouble is that you begin running into limits for the size of your value as well as the length of your array. -- Switching to a string or bitarray implementation helps, but you still have the challenge of iterating through your list at large values.

Answer 3

You can find four different Erlang implementations for finding prime numbers (two of which are based on the Sieve of Eratosthenes) here. This link also contains graphs comparing the performance of the 4 solutions.

Answer 4

Two quick single-process erlang prime generators; sprimes generates all primes under 2m in ~2.7 seconds, fprimes ~3 seconds on my computer (Macbook with a 2.4 GHz Core 2 Duo). Both are based on the Sieve of Eratosthenes, but since Erlang works best with lists, rather than arrays, both keep a list of non-eliminated primes, checking for divisibility by the current head and keeping an accumulator of verified primes. Both also implement a prime wheel to do initial reduction of the list.

-module(primes).
-export([sprimes/1, wheel/3, fprimes/1, filter/2]).    

sieve([H|T], M) when H=< M -> [H|sieve([X || X<- T, X rem H /= 0], M)];
sieve(L, _) -> L.
sprimes(N) -> [2,3,5,7|sieve(wheel(11, [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10], N), math:sqrt(N))].

wheel([X|Xs], _Js, M) when X > M ->
    lists:reverse(Xs);
wheel([X|Xs], [J|Js], M) ->
    wheel([X+J,X|Xs], lazy:next(Js), M);
wheel(S, Js, M) ->
    wheel([S], lazy:lazy(Js), M).

fprimes(N) ->
    fprimes(wheel(11, [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10], N), [7,5,3,2], N).
fprimes([H|T], A, Max) when H*H =< Max ->
    fprimes(filter(H, T), [H|A], Max);
fprimes(L, A, _Max) -> lists:append(lists:reverse(A), L).

filter(N, L) ->
    filter(N, N*N, L, []).
filter(N, N2, [X|Xs], A) when X < N2 ->
    filter(N, N2, Xs, [X|A]);
filter(N, _N2, L, A) ->
    filter(N, L, A).
filter(N, [X|Xs], A) when X rem N /= 0 ->
    filter(N, Xs, [X|A]);
filter(N, [_X|Xs], A) ->
    filter(N, Xs, A);
filter(_N, [], A) ->
    lists:reverse(A).

lazy:lazy/1 and lazy:next/1 refer to a simple implementation of pseudo-lazy infinite lists:

lazy(L) ->
    repeat(L).

repeat(L) -> L++[fun() -> L end].

next([F]) -> F()++[F];
next(L) -> L.

Prime generation by sieves is not a great place for concurrency (but it could use parallelism in checking for divisibility, although the operation is not sufficiently complex to justify the additional overhead of all parallel filters I have written thus far).

`