| Author |
Message |
< Erlang ~ Sum primes in a range concurrently |
| kevinjq |
 Posted: Mon Jun 01, 2009 4:09 pm |
 |
|
|
Joined: 01 Jun 2009
Posts: 3
|
Hi all, I'm new to Erlang. I'm trying to solve the problem of summing all the prime numbers under 2 million (yes, it's from project euler). Everyone knows the brute-force way takes forever, and it doesn't utilize the multi-core nature of modern computers. So I figure I'll have a try using Erlang's concurrency oriented programming model to solve this.
Basically, I have three actors in my system:
solve -> the entry point of the program
worker -> the process that sums all the prime numbers in a given range (relatively small ~100, which can be computed in a fairly short amount of time)
tallier -> the process that waits for workers to report their result and compute the final tally.
Here's the code for worker:
Code:
worker() ->
receive
{TallierPid, L} ->
[H|_] = L,
Sum = sum_prime_in_range(L),
TallierPid ! {self(), H, Sum}
end.
sum_prime_inrange(List) ->
lists:sum(lists:filter(fun(X)->mylib:is_prime(X) end, List)).
Tallier:
Code:
tallier(X) ->
receive
{_, H, Sum} ->
Tally = X + Sum,
io:format(T: Group~p,X=~p~n", [H, X+Sum]),
tallier(Tally)
end.
Solver:
Code:
solver(TallierPid, From, To) ->
case (To - From) of
SmallRange when SmallRange =< 1000 ->
List = lists:seq(From, To),
WorkerPid = spawn(fun worker/0),
WorkerPid ! {TallierPid, List};
_ ->
Mid = mylib:floor((To+From) div 2),
solver(TallierPid, From, Mid),
solver(TallierPid, Mid+1, To)
end.
Basically, solver is a recursive function that splits the range in halves everytime until the range is deemed small enough.
solve:
Code:
solve() ->
TallierPid = spawn(mymod, tallier, [0]),
solver(TallierPid, 2, 2000000).
The program runs and it does compute the sum correctly and quickly and the most exciting thing is in the system process manager, both CPU cores are fully utilized. However, for range 2 million, it still seems to take forever to compute. I didn't leave the program to run very long, though, as I was afraid that keeping both cores to run at 100% may be harmful to my CPU.
Any ideas where I may have done wrong? |
|
|
| Back to top |
 
|
| kevinjq |
| Posted: Mon Jun 01, 2009 5:44 pm |
|
|
|
Joined: 01 Jun 2009
Posts: 3
|
| I just realized that my is_prime function is too inefficient...I changed the implementation of is_prime function and now adding the primes under 2 million only takes 5 seconds! Whoah!! Just had a first-hand experience with how powerful it is! |
|
|
| Back to top |
|
| Mazen |
| Posted: Mon Jun 01, 2009 7:43 pm |
|
|
|
User
Joined: 20 Jul 2006
Posts: 164
Location: London
|
Post code if you want 
Some of us might be curious of how it is implemented
EDIT: Eeeerr.... English! |
Last edited by Mazen on Tue Jun 02, 2009 8:19 am; edited 1 time in total |
|
| Back to top |
|
| kevinjq |
| Posted: Tue Jun 02, 2009 3:47 am |
|
|
|
Joined: 01 Jun 2009
Posts: 3
|
Mazen wrote: Post code if you want
Some of might be curious of how it is implemented
I've written a blogpost about it. I'm still quite new to erlang (http://www.dzone.com/links/fast_and_elegant_way_to_sum_primes_in_a_gigantic.html) so maybe someone has a better solution. |
|
|
| Back to top |
|
|
|
All times are GMT
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
|
|
|
Digg It
Del.icio.us
Reddit
Facebook
Stumble Upon
Technorati
