beginner needs help with sieve program
Doug Bagley
doug@REDACTED
Mon Sep 4 00:24:19 CEST 2000
Hi, I just started learning about erlang a couple days ago. The first
thing I wanted to do was to see how efficiently I could program a
sieve of eratosthenes for numbers 2 to 8192.
Basically I need help finding the bug in the first attempt and I'd
also be interested if anyone has suggestions on how to write a speedy
sieve.
The following is my first attempt, which has runtimes that compare
favorably with Perl, Tcl, Python and Guile, but it has a bug in it:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% sieve.erl
% I run it like this:
% > erl -compile sieve ; erl -noinput -s sieve main 100
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-module(sieve).
-export([main/1]).
-import(io, [fwrite/2]).
-import(lists, [seq/2, filter/2]).
-import(math, [sqrt/1]).
%% get the program argument, which is how many test iterations
%% to run
main(Args) ->
[Tmp] = Args,
Iter = list_to_integer(atom_to_list(Tmp)),
test(Iter),
halt(0).
%% run the test N times
test(N) ->
Primes = sieve(8192),
%% there is a bug in our sieve which lets says 2197 is prime
%% but it is not, it is a multiple of 13
%% all the other 1028 primes in the list are okay though
%% so i fudge the correct answer for now
Count = length(Primes) - 1,
case N > 1 of
true -> test(N-1);
false -> fwrite("Count: ~w\n", [Count])
end.
sieve(Size) ->
sieve(2, sqrt(Size), seq(2,Size)).
sieve(Start, End, Seq) ->
case Start > End of
true -> Seq;
false -> sieve(Start + 1, End, remove_multiples(Start, Start+Start, Seq))
end.
%% remove multiples of Num from a list without using modulus
%% I've rewritten this 2 different ways using case
%% and I get the same results
remove_multiples(Num, Next, [H|T]) when H < Next ->
[H | remove_multiples(Num, Next, T)];
remove_multiples(Num, Next, [H|T]) when H == Next ->
remove_multiples(Num, Next+Num, T);
remove_multiples(Num, Next, [H|T]) when H > Next ->
[H | remove_multiples(Num, Next+Num, T)];
remove_multiples(X, Y, []) -> [].
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The next attempt was to use modulus and write it in a very short,
hopefully, erlang way. This produces correct results, but is
incredibly slow.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% sieve.erl
% I run it like this:
% > erl -compile sieve ; erl -noinput -s sieve main 100
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-module(sieve).
-export([main/1]).
-import(io, [fwrite/2]).
-import(lists, [seq/2, filter/2]).
main(Args) ->
[Tmp] = Args,
Iter = list_to_integer(atom_to_list(Tmp)),
test(Iter),
halt(0).
test(N) ->
Primes = sieve(8192),
Count = length(Primes),
case N > 1 of
true -> test(N-1);
false -> fwrite("Count: ~w\n", [Count])
end.
sieve(Size) -> sievel(seq(2,Size)).
sievel([H|T]) -> [H | sievel(filter(fun(N) -> N rem H > 0 end, T))];
sievel([]) -> [].
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
More information about the erlang-questions
mailing list