Tuesday, February 03, 2009

Prime Factorization Using Concurrent Processes in Erlang

Well, I started doing the Project Euler problems again using Erlang and I got to one that required factorization, so I re-did problem number 3. After trying the solution advertised, I did a bit of research and I came across the Sieve of Eratosthenes. It was very simple to implement, so I used that to do the factorization. It was pretty simple and seemed to be reasonable fast.

Well, I was thinking of trying to speed up the sieve, mainly by trying to parallelize parts of it. Yep. I'm thinking more about processes as the days go on. Well, it hit me yesterday that by using the sieve to create prime numbers that I then try to use to factor a number, I could generate the prime numbers in parallel to testing to see if they're a factor. Not sure if it's any faster than the single-threaded version, especially since I'm doing this in a virtual machine, however I'm guessing that if I do get this on a multi-core machine, it should be somewhat faster.

Here's the code for anyone who's interested.

pfactor(N) ->
SN = round(math:sqrt(N)),
P = spawn_link(factor, pfactor1, [N, []]),
spawn_link(factor, pseive, [lists:seq(2, SN), P]).

pfactor1(N, Factors) ->
io:format("In pfactor1.~n"),
{factor, Factor} ->
io:format("Received a factor: ~p~n", [Factor]),
(N rem Factor) == 0 ->
pfactor1(N, Factors ++ [Factor]);
true ->
pfactor1(N, Factors)
{done, []} ->
io:format("Factors: ~p~n", [Factors])
after 10000 ->
io:format("Timed out...~n")

pseive([P | R], Pid) ->
io:format("Sending the new factor: ~p~n", [P]),
Pid ! {factor, P},
pseive([X || X <- R, (X rem P) > 0], Pid);
pseive([], Pid) ->
io:format("All done...~n"),
Pid ! {done, []}.

Labels: , ,


Post a Comment

Links to this post:

Create a Link

<< Home