Saturday, October 6, 2007

Sieve of Eratosthenes

People whom studied computer science has heard of the "Sieve of Eratosthenes" and i took the implementation in Erlang as an exercise and collected the run-times of the program to determine the number of primes less than 120, 1000, 10000, 100000 and 1000000.


Filename: "sieve.erl"
-module(sieve).
-export([findPrimes/1, genmulti/3, removeMultiples/3]).

%
% The following generates a list of multiples-of-Base
% e.g. To generate multiples of 3 less than 100, enter "sieve:genmulti(0,3,100)"
% and you get [9,12,15,18|...]
%
genmulti(Index,Base,Limit) when (Base*Base+Index*Base) > Limit -> [];
genmulti(Index,Base,Limit) when (Base*Base+Index*Base) =<> [Base*Base+Index*Base | genmulti(Index+1,Base,Limit) ].

removeMultiples(Index, List, Limit) when Index /= erlang:length(List) ->
Head = lists:nth(Index,List),
NewList = List -- genmulti(0,Head,Limit),
removeMultiples(Index+1, NewList, Limit);
removeMultiples(Index, List, _) when Index =:= erlang:length(List) -> List.

findPrimes(Num) -> List = lists:seq(2,Num),
statistics(runtime),
statistics(wall_clock),
FinalList = removeMultiples(1, List, lists:max(List)),
{_, Time1} = statistics(runtime),
{_, Time2} = statistics(wall_clock),
io:format("Total discovered primes:~w~n", [erlang:length(FinalList)]),
io:format("Runtime:~w(s) Wall-clock Time:~w(s)~n", [Time1/1000, Time2/1000]),
lists:foreach( fun(X) -> io:format("~w, ", [X]) end, FinalList).

To run this, there are a few ways you can do this in Erlang but the most common is the following:
1/ Copy-paste the code into a file of your choice, in my case its "sieve.erl"
2/ Start a Erlang shell
3/ Compile the program via "c(sieve)."
4/ Execute the program via "sieve:findPrimes(120)" which is to find the number of primes numbers less than or equal to 120.

My program will reveal how many primes have been discovered and the computation time it took and you can counter check the number of primes discovered against this site How Many Primes Are There?

Finally, the run-times for discovering the number of primes less than 120, 1000, 10000, 100000 and 1000000 are displayed below.


sieve:findPrimes(120).
Total discovered primes:30
Runtime:0.00000e+0(s) Wall-clock Time:0.00000e+0(s)

sieve:findPrimes(1000).
Total discovered primes:168
Runtime:1.00000e-2(s) Wall-clock Time:9.00000e-3(s)

sieve:findPrimes(10000).
Total discovered primes:1229
Runtime:0.290000(s) Wall-clock Time:0.295000(s)

sieve:findPrimes(100000).
Total discovered primes:9592
Runtime:29.8900(s) Wall-clock Time:30.0060(s)

sieve:findPrimes(1000000).
Total discovered primes:78498
Runtime:3025.86(s) Wall-clock Time:3042.31(s)

2 comments:

Unknown said...

I've only been learning erlang a few weeks but your solution seems needlessly verbose and slow :)

1. You're generating lists needlessly. Get rid of the genmulti method.
2. Try to avoid using the -- and ++ operators because you're traversing the length of the first list each time you use them.
3. List generators can save you a lot of code.

Here's my solution:
eratosthenes(Lim) -> eratosthenes(lists:seq(2,Lim), 1).
eratosthenes([], Primes) -> Primes;
eratosthenes([H|T], Primes) -> eratosthenes([X || X <- T, X rem H /= 0], Primes + 1).

Raymond Tay said...

Hi James,

Like your solution! Its much cleaner and faster :) nice work. Thanks for the suggestions and like you i was just starting out to learning erlang and exposing myself to functional programming for the first time :) guess i have a lot to learn!

Take care,
Ray