Showing posts with label Sieve of Eratosthenes. Show all posts
Showing posts with label Sieve of Eratosthenes. Show all posts

Monday, October 29, 2007

Core Erlang + "GS" = GUI version of the "Sieve"

In this article, i want to demonstrate a bit more about the G.S. Previously, i wrote an extremely simple Erlang Window just to see how it easy it was, apparently it's not very difficult.

What i subsequently did was to combine the both the "GS" and the Sieve of Eratosthenes to produce a graphical version of the "sieving" problem. The point of this exercise was to illustrate how easy it was to code in Erlang once you have gotten used to its semantics, i had fun doing it.

Owing to my laptop's screen resolution, i could only manage a 25-by-25 grid but that's not the point of this exercise. Here are some screen shots and a working code (Code needs to be smoothen though, let me know your comments)

%
% This is an attempt to create a GUI version of the "Sieve of Erasothenes'
%
%
-module(sievegui).
-export([start/0, init/1]).
-copyright('Copyright (c) 2007 Raymond Tay').
-vsn('$Revision: 1').
%
% 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) =< Limit -> [Base*Base+Index*Base | genmulti(Index+1,Base,Limit) ].

sleep(T) ->
receive
after T -> ok
end.
%
% Obtains the GS's "object id" and manipulates the display
%
filterDisplay(ObjId,List) ->
{_,ObjValue} = gs:read(ObjId, label),
{IntValue,X} = string:to_integer(ObjValue),
Result = lists:member(IntValue,List),
if
Result =:= true -> gs:config(ObjId,[{label, {text, ""}}]);
Result =:= false -> ok
end,
sleep(50).
% filterDisplay(ObjId,List) ->
% {_,ObjValue} = gs:read(ObjId, label),
% Result = lists:member(ObjValue,List),
% if
% Result =:= true -> gs:config(ObjId,[{label, {text, ""}}])
% end.

removeMultiples(Index, List, Limit, Dict) when Index /= erlang:length(List) ->
Head = lists:nth(Index,List),
RemoveList = genmulti(0,Head,Limit),
Keys = dict:fetch_keys(Dict),
lists:foreach( fun(X) -> filterDisplay(X,RemoveList) end, Keys),
NewList = List -- RemoveList,
removeMultiples(Index+1, NewList, Limit, Dict);
removeMultiples(Index, List, _, _) when Index =:= erlang:length(List) -> List.


%
% A standard Erlang "for"-loop
%
for(N,N,F) -> F();
for(I,N,F) -> F(),for(I+1,N,F).

forL(N,N,{stretch,_N,_X}) -> [{stretch,_N,_X}];
forL(I,N,{stretch,_N,_X}) -> [{stretch,_N,_X}|forL(I+1,N,{stretch,_N,_X})].
%
% start() -> You can call this if you wish; the only difference between this and init() is that start() starts
% a spawned process
%
start() -> spawn(gsdemo, init, [625]).

%
% Generates the GUI for the button
% where the label for each button is that of incremental number
%
genBut(Row,Col,Text,Dict) when Row*Col =< 625 ->
if
Col =< 25 ->
%io:format("R:~p,C:~p,T:~p~n", [Row,Col,erlang:integer_to_list(Text,10)]),
ButId = gs:button(packer, [{label, {text, erlang:integer_to_list(Text,10)}}, {pack_xy, {Col,Row}}]),
NewDict = dict:store(ButId, ButId, Dict),
NewText = Text+1,
genBut(Row,Col+1, NewText, NewDict);
Col > 25 -> genBut(Row+1, 1, Text, Dict)
end;
genBut(Row,Col,_Text, Dict) when Row*Col > 625 -> Dict.

%
% init() - You can call this if you wish
%
init(Num) ->
_Dict = dict:new(), % process dictionary
WH = [{width, 800}, {height, 800}],
Win = gs:window(gs:start(), [{map, true}, {configure, true}, {title, "Sieve of Erasothenes"} |WH]),
XOpts = forL(1,25,{stretch,1,8}),
YOpts = forL(1,25,{stretch,1,8}),
gs:frame(packer, Win, [{packer_x, XOpts}, {packer_y, YOpts}]),
NewDict = genBut(1,1,2,_Dict),
gs:config(packer, WH), %refresh to initial size
List = lists:seq(2,Num),
FinalList = removeMultiples(1, List, lists:max(List), NewDict),
loop().
%
% A typical loop for receiving messages
%
loop() ->
receive
{gs,_Id,destroy,_Data,_Arg} -> bye;
Other -> loop()
end.
There are three screenshots below of this application to illustrate the program sieving through the numbers

That's it, all comments are welcome.

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)