[erlang-questions] Hi all here the RESUME for Pytagorians Numbers Algorithm!!!

Edmond Begumisa <>
Mon Nov 15 17:30:27 CET 2010


It's interesting to see that parallelising on a single core comes at 0  
cost. Why did I think parallel versions would be slightly slower on a  
single core machine? I was even tempted to put in a test and only go  
parallel if there's more than one core.

BTW, are you sure your py2 algo is wrong or does it just return the list  
in a different order? Try sorting the lists before the =:= test.

- Edmond -

On Mon, 15 Nov 2010 15:25:24 +1100, Gilberio Carmenates García  
<> wrote:

>
>   Made on a pc with Petium 4 CPU 1.6 Ghz one core, 512 Ram.
>
> *** Pytagoriam's Numbers REPORT! ***
>
> Using N = 300
>
> *** THE ORIGINAL IMPLEMENTATIONS (ME!)****
> -py1:         15547000 mcs = 15.547 s
> -py2:         14514999 mcs = 14.514999 s
> -py3:         14468999 mcs = 14.468999 s
>
> *** Tony's implementations ****
> -pythag1:     13218999 mcs = 13.218999 s
> -pythag2:     2296999 mcs = 2.296999 s
>
> *** Hynek's implementation ****
> Simpler and about 5% faster version
> -pythag3:     2202999 mcs = 2.202999 s
>
> *** Edmond's implementation, using parallelism****
> -py2E:        14624999 mcs = 14.624999 s
>
> *** Willem's implementation****
> -wpythag2:    2202999 mcs = 2.202999 s
>
> *** Hynek's new implementation****
> -pythag4:     1530999 mcs = 1.530999 s
>
> *** Willem's new implementation in parallel by Hynek****
> -wpythag2P:   2202999 mcs = 2.202999 s
>
> *** Morten's implementation****
> -pythag5:     62999 mcs = 0.062999 s
>
> *** Richard's improvement****
> -py3R:        2452999 mcs = 2.452999 s
>
> Comparisons in results agains 'pythag1' Tony's function
> py1 returns the same than 'pythag1'
> py2 NO returns the same than 'pythag1'       %% since my secound
> implementation 'py2' is wrong!!!
> py3 returns the same than 'pythag1'
> pythag1 returns the same than 'pythag1'
> pythag2 returns the same than 'pythag1'
> pythag3 returns the same than 'pythag1'
> py2E NO returns the same than 'pythag1'      %% since Edmond use my
> wrong implementation.
> wpythag2 returns the same than 'pythag1'
> pythag4 returns the same than 'pythag1'
> wpythag2P returns the same than 'pythag1'
> pythag5 returns the same than 'pythag1'
> py3R NO returns the same than 'pythag1'     %% I just tries to put the
> Richard explanation in a
>                                                 algorithm but, seems to
> me I was wrong here too.
>
> NOTE: Time was took using timer:tc/3 function.
>
>
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Here the source code of all algorithm
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
>
>
> -module(py).
> -compile([export_all]).
>
>
> start(N)->
>      %% My implementations.
>      {T1,R1} = timer:tc(py,py1, [N]),
>      {T2,R2} = timer:tc(py,py2,[N]),
>      {T3,R3} = timer:tc(py,py3,[N]),
>
>      %% Tony's improvement of the original form 3.
>      {T4,R4} = timer:tc(py,pythag1,[N]),
>      %% Tony's implementation.
>      {T5,R5} = timer:tc(py,pythag2,[N]),
>
>      %% Hynek's implementation.
>      %% Simpler and about 5% faster version:
>      {T6,R6} = timer:tc(py,pythag3,[N]),
>
>      %% Edmond's implementation using parallelism.
>      {T7,R7} = timer:tc(py,py2E,[N]),
>
>      %% Willem's implementation.
>      {T8,R8} = timer:tc(py,wpythag2,[N]),
>
>      %% Hynek's new version
>      {T9,R9} = timer:tc(py,pythag4,[N]),
>
>      %% Willem's implementation in parallel by Hynek
>      {T10,R10} = timer:tc(py,wpythag2P,[N]),
>
>      %% Morten's implementation.
>      {T11,R11} = timer:tc(py,pythag5,[N]),
>
>      %% Richard's improvement.
>      {T12,R12} = timer:tc(py,py3R,[N]),
>
>      io:format("~n *** Pytagoriam's Numbers REPORT! ***~n~n"),
>      io:format("Using N = ~p~n", [N]),
>
>      io:format("~n*** THE ORIGINAL IMPLEMENTATIONS (ME!)****~n"),
>      io:format("-py1:         ~p mcs = ~p s~n", [T1,T1/1000000]),
>      io:format("-py2:         ~p mcs = ~p s~n", [T2,T2/1000000]),
>      io:format("-py3:         ~p mcs = ~p s~n", [T3,T3/1000000]),
>
>      io:format("~n*** Tony's implementations ****~n"),
>      io:format("-pythag1:     ~p mcs = ~p s~n", [T4,T4/1000000]),
>      io:format("-pythag2:     ~p mcs = ~p s~n", [T5,T5/1000000]),
>
>      io:format("~n*** Hynek's implementation ****~n"),
>      io:format("Simpler and about 5% faster version~n"),
>      io:format("-pythag3:     ~p mcs = ~p s~n", [T6,T6/1000000]),
>
>      io:format("~n*** Edmond's implementation, using parallelism****~n"),
>      io:format("-py2E:        ~p mcs = ~p s~n", [T7,T7/1000000]),
>
>      io:format("~n*** Willem's implementation****~n"),
>      io:format("-wpythag2:    ~p mcs = ~p s~n", [T8,T8/1000000]),
>
>      io:format("~n*** Hynek's new implementation****~n"),
>      io:format("-pythag4:     ~p mcs = ~p s~n", [T9,T9/1000000]),
>
>      io:format("~n*** Willem's new implementation in parallel by
> Hynek****~n"),
>      io:format("-wpythag2P:   ~p mcs = ~p s~n", [T10,T10/1000000]),
>
>      io:format("~n*** Morten's implementation****~n"),
>      io:format("-pythag5:     ~p mcs = ~p s~n", [T11,T11/1000000]),
>
>      io:format("~n*** Richard's improvement****~n"),
>      io:format("-py3R:        ~p mcs = ~p s~n", [T12,T12/1000000]),
>
>      io:format("~nComparisons in results agains 'pythag1' Tony's
> function~n"),
>      Rs = [{py1,R1}, {py2,R2}, {py3,R3}, {pythag1,R4}, {pythag2,R5},
> {pythag3,R6},
>            {py2E,R7}, {wpythag2,R8}, {pythag4,R9}, {wpythag2P,R10},
> {pythag5,R11}, {py3R,R12}],
>      lists:foreach(fun({Name, R})->
>          if
>              (R=:=R4)->
>                  io:format("~p returns the same than 'pythag1'~n",  
> [Name]);
>              true->
>                  io:format("~p NO returns the same than 'pythag1'~n",
> [Name])
>          end
>      end, Rs),
>      io:format("~nNOTE: Time took using timer:tc/3 function.~n").
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% The original form 1.
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> py1(Max)->
>      L = lists:seq(1, Max),
>      lists:foldr(
>          fun(A, Acc3)->
>              lists:foldr(
>                  fun(B, Acc2)->
>                      lists:foldr(
>                          fun(C, Acc)->
>                              case ((A*A + B*B =:= C*C) andalso (A+B+C =<
> Max)) of
>                                  true->
>                                      [{A,B,C}|Acc];
>                                  false->
>                                      Acc
>                              end
>                          end
>                      , Acc2, L)
>                  end
>              , Acc3, L)
>          end
>      , [], L).
>
>
>
> %% The original form 2.
> py2(Max)->
>      fora(1, [], Max).
>
> fora(A, Acc, Max)->
>      Acc1 = forb(A,1, Acc, Max),
>      case A<  Max of
>          true->
>              fora(A+1, Acc1, Max);
>          false->
>              Acc1
>      end.
>
> forb(A,B, Acc, Max)->
>      Acc1 = forc(A,B,1, Acc, Max),
>      case B<  Max of
>          true->
>              forb(A,B+1, Acc1, Max);
>          false->
>              Acc1
>      end.
>
> forc(A,B,C, Acc, Max)->
>      Acc1 = case (A*A + B*B =:= C*C) andalso (A+B+C =<  Max) of
>          true->
>              [{A,B,C}|Acc];
>          _->
>              Acc
>      end,
>      case C<  Max of
>          true->
>              forc(A,B,C+1, Acc1, Max);
>          false->
>              Acc1
>      end.
>
> %% The original form 3.
> py3(Max)->
>      [{A,B,C} ||
>          A<-lists:seq(1, Max),
>          B<-lists:seq(1, Max),
>          C<-lists:seq(1, Max),
>          A*A + B*B =:= C*C,
>          A+B+C =<  Max].
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Tony's improvement of the original form 3.
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> pythag1(N) ->
>      L = lists:seq(1,N),
>      [ {A,B,C} ||
>          A<- L,
>          B<- L,
>          C<- L,
>          A+B+C =<  N,
>          A*A+B*B =:= C*C].
>
> %% Tony's implementation.
> pythag2(N) ->
>      lists:reverse(pythan2_A(1, N, [])).
>
> pythan2_A(A, N, Acc) when A>  N ->  Acc;
> pythan2_A(A, N, Acc) ->  pythan2_A(A+1,N,pythan2_B(A, 1, N, Acc)).
>
> pythan2_B(A, B, N, Acc) when A+B>  N ->  Acc;
> pythan2_B(A, B, N, Acc) ->  pythan2_B(A,B+1,N,pythan2_C(A, B, 1, N,  
> Acc)).
>
> pythan2_C(A, B, C, N, Acc) when A+B+C>  N ->  Acc;
> pythan2_C(A, B, C, N, Acc) ->
>      if A*A+B*B =:= C*C ->
>          pythan2_C(A, B, C+1, N, [{A,B,C}|Acc]);
>      true ->
>          pythan2_C(A, B, C+1, N, Acc)
>      end.
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Hynek's implementation.
> %% Simpler and about 5% faster version:
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> pythag3(N) when is_integer(N) ->  pythag3(N,1).
>
> pythag3(N, A) when A+2>  N ->  [];
> pythag3(N, A) ->  pythag3(N, A, 1).
>
> pythag3(N, A, B) when A+B+1>  N ->  pythag3(N, A+1);
> pythag3(N, A, B) ->  pythag3(N, A, B, 1).
>
> pythag3(N, A, B, C) when A+B+C>  N ->  pythag3(N, A, B+1);
> pythag3(N, A, B, C) when A*A + B*B =:= C*C ->  [{A, B, C}|pythag3(N, A,
> B, C+1)];
> pythag3(N, A, B, C) ->  pythag3(N, A, B, C+1).
>
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Edmond's implementation using parallelism.
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> %%---- START CODE ----
>
> py2E(Max)->
>      lists:flatten(lpmap(fun(A) ->
>                              forbE(A, 1, [], Max)
>                          end, lists:seq(1, Max), ordered)).
>
> forbE(A, B, Acc, Max) ->
>      Acc1 = forcE(A, B, 1, Acc, Max),
>      case B<  Max of
>          true ->  forbE(A, B+1, Acc1, Max);
>          false ->  Acc1
>      end.
>
> forcE(A, B, C, Acc, Max) ->
>      Acc1 = case (A*A + B*B =:= C*C) andalso (A+B+C =<  Max) of
>                  true ->  [{A,B,C}|Acc];
>                  _ ->  Acc
>             end,
>      case C<  Max of
>          true->  forcE(A, B, C+1, Acc1, Max);
>          false->  Acc1
>      end.
>
>
> pythag2E(N)->
>      lists:flatten(lpmap(fun(A) ->
>                              pythan2_BE(A, 1, N, [])
>                          end, lists:seq(1, N), ordered)).
>
> pythan2_AE(A, N, Acc) when A>  N ->  Acc;
> pythan2_AE(A, N, Acc) ->  pythan2_AE(A+1,N,pythan2_BE(A, 1, N, Acc)).
>
> pythan2_BE(A, B, N, Acc) when A+B>  N ->  Acc;
> pythan2_BE(A, B, N, Acc) ->  pythan2_BE(A,B+1,N,pythan2_CE(A, B, 1, N,
> Acc)).
>
> pythan2_CE(A, B, C, N, Acc) when A+B+C>  N ->  Acc;
> pythan2_CE(A, B, C, N, Acc) ->
>      if A*A+B*B =:= C*C ->
>          pythan2_CE(A, B, C+1, N, [{A,B,C}|Acc]);
>         true ->
>          pythan2_CE(A, B, C+1, N, Acc)
>      end.
>
> %% @spec    lpmap(fun(), list(), (atom() = ordered|unordered)) ->  list()
> %% @doc     Spawns a process for each element in list L, performs  
> specified
> %%          function F against each in parallel and then returns results
> either
> %%          same order as L (ordered) or in any order (unordered).
> %%          NB: See also lpmap/4.
>
> lpmap(F, L, ordered) ->
>      Ref = erlang:make_ref(),
>      Pids = [lpmap_spawn_link(self(), Ref, F, I) || I<- L],
>      lpmap_gather_ordered(Pids, Ref, [], 0, void);
> lpmap(F, L, unordered) ->
>      Ref = erlang:make_ref(),
>      lists:foreach(fun(I) ->
>                      lpmap_spawn_link(self(), Ref, F, I)
>                    end, L),
>      lpmap_gather_unordered(length(L), Ref, [], 0, void).
>
> %% @spec    lpmap(fun(), integer(), list(), (atom() =
> ordered|unordered)) ->  list()
> %% @doc     Same as lpmap/3 except ensures only a maximum of MaxPs  
> parallel
> %%          processes execute function F at any one time (i.e. first
> takes MaxPs
> %%          items from list, executes F in parallel against each, then
> as each
> %%          process returns, spawns another process on next item in L as
> long as
> %%          active processes are less than MaxPs).
> %%          NB: See also lpmap/4.
>
> lpmap(F, L, MaxPs, ordered) when MaxPs>0 ->
>      Ref = erlang:make_ref(),
>      {HPids, TPids} = if
>                          length(L)>  MaxPs ->  lists:split(MaxPs, L);
>                          true ->  {L, []}
>                       end,
>      Pids = [lpmap_spawn_link(self(), Ref, F, I) || I<- HPids],
>      lpmap_gather_ordered(Pids, Ref, TPids, MaxPs, F);
> lpmap(F, L, MaxPs, unordered) when MaxPs>0 ->
>      Ref = erlang:make_ref(),
>      {HPids, TPids} = if
>                          length(L)>  MaxPs ->  lists:split(MaxPs, L);
>                          true ->  {L, []}
>                       end,
>      lists:foreach(fun(I) ->
>                      lpmap_spawn_link(self(), Ref, F, I)
>                    end, HPids),
>      lpmap_gather_unordered(length(HPids), Ref, TPids, MaxPs, F).
>
> %% lpmap internal functions
>
> lpmap_spawn_link(Parent, Ref, F, I) ->
>      spawn_link(fun() ->
>                      Parent ! {self(), Ref, F(I)}
>                 end).
>
> lpmap_gather_ordered([], _Ref, [], _MaxPs, _F) ->
>      [];
> lpmap_gather_ordered([HPid|TPids], Ref, L, MaxPs, F) ->
>      receive
>          {HPid, Ref, Ret} when length(TPids)<MaxPs, L=/=[] ->
>              [H | T] = L,
>              [Ret | lpmap_gather_ordered(
>                  lists:append(TPids, [lpmap_spawn_link(self(), Ref, F,
> H)]),
>                  Ref, T, MaxPs, F)];
>          {HPid, Ref, Ret} ->
>              [Ret | lpmap_gather_ordered(TPids, Ref, L, MaxPs, F)]
>      end.
>
> lpmap_gather_unordered(0, _Ref, [], _MaxPs, _F) ->
>      [];
> lpmap_gather_unordered(NPs, Ref, L, MaxPs, F) ->
>      receive
>          {_Pid, Ref, Ret} when NPs-1<MaxPs, L=/=[] ->
>              [H | T] = L,
>              lpmap_spawn_link(self(), Ref, F, H),
>              [Ret | lpmap_gather_unordered(NPs, Ref, T, MaxPs, F)];
>          {_Pid, Ref, Ret} ->
>              [Ret | lpmap_gather_unordered(NPs-1, Ref, L, MaxPs, F)]
>      end.
>
>
> %%---- END CODE -----
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Willem's implementation.
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> wpythag2(N) ->
>     L = [{A, A*A} || A<- lists:seq(1,N)],
>     lists:flatten([forAllBs(A, A2, L, N) || {A, A2}<- L]).
>
> forAllBs(A, A2, L, N) ->
>    [forAllCs(A, B, A + B, A2 + B2, L, N) || {B, B2}<- L, A + B<  N].
>
> forAllCs(A, B, AB, A2B2, L, N) ->
>    [{A, B, C} || {C, C2}<- L, A2B2 =:= C2, AB + C =<  N].
>
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Hynek's new version
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> pythag4(N) when is_integer(N) ->  pythag4(N,1).
>
> pythag4(N, A) when A+2>  N ->  [];
> pythag4(N, A) ->  pythag4(N, A, A*A, 1).
>
> pythag4(N, A, _A2, B) when A+B+1>  N ->  pythag4(N, A+1);
> pythag4(N, A, A2, B) ->  pythag4(N, A, A2, B, B*B, 1).
>
> pythag4(N, A, A2, B, _B2, C) when A+B+C>  N ->  pythag4(N, A, A2, B+1);
> pythag4(N, A, A2, B, B2, C) when A2 + B2 =:= C*C ->
>    [{A, B, C}|pythag4(N, A, A2, B, B2, C+1)];
> pythag4(N, A, A2, B, B2, C) ->  pythag4(N, A, A2, B, B2, C+1).
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Willem's implementation in parallel by Hynek
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> wpythag2P(N) ->
>      L = [{A, A*A} || A<- lists:seq(1,N)], % For all A's
>      lists:flatten(lpmap(fun({A, A2}) ->     % For all B's in parallel
>                              [forAllCsWH(A, B, A + B, A2 + B2, L, N)
>                                          || {B, B2}<- L, A + B<  N]
>                          end, L, 2000, ordered)).
>
> forAllCsWH(A, B, AB, A2B2, L, N) ->
>      [{A, B, C} || {C, C2}<- L, A2B2 =:= C2, AB + C =<  N].
>
>
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Morten's implementation.
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> pythag5(N) when is_integer(N) ->
>    Primes = sieve(N div 2),
>    M1M2s = incorporate_primes([{1,1}], N, Primes),
>    lists:usort(lists:flatten([ [{A,B,C}, {B,A,C}] || {M1, M2}<- M1M2s,
> M1>  M2, A<- [M1-M2], B<- [2*round(math:sqrt(M1*M2))], C<- [M1+M2],
> A+B+C =<  N])).
>
> sieve(N) when is_integer(N) ->
>    erase(),
>    sieve(N,2).
>
> sieve(N, K) when K>= N ->
>   [X || X<- lists:seq(2, N), erase(X) == undefined];
> sieve(N, K) ->
>    cross_off(K, K, N div K - 1),
>    sieve(N, find_next_in_sieve(K + 1)).
>
> cross_off(_K, _Current, 0) ->
>    ok;
> cross_off(K, Current, Left) ->
>    Next = Current + K,
>    put(Next, out),
>    cross_off(K, Next, Left - 1).
>
> find_next_in_sieve(K) ->
>    case get(K) of
>      undefined ->
>        K;
>      _ ->
>        find_next_in_sieve(K+1)
>    end.
>
> incorporate_prime(M1M2s, N, P) ->
>    lists:flatten([incorporate_prime_single({M1,M2}, N, P)|| {M1, M2}<-
> M1M2s]).
>
> incorporate_prime_single({M1,M2}, N, P) ->
>    Evens = [{X, Y} || X<- incorporate_prime_even(M1, N, P), Y<-
> incorporate_prime_even(M2, N, P)],
>    Odds = [{X, Y} || X<- incorporate_prime_odd(M1, N, P), Y<-
> incorporate_prime_odd(M2, N, P)],
>    Evens ++ Odds.
>
> incorporate_prime_even(M, N, P) ->
>    incorporate_prime(M, N, P, []).
>
> incorporate_prime_odd(M, N, P) ->
>    incorporate_prime(M * P, N, P, []).
>
> incorporate_prime(M, N, _P, Acc) when M>  N/2 ->
>    Acc;
> incorporate_prime(M, N, P, Acc) ->
>    incorporate_prime(M * P * P, N, P, [M|Acc]).
>
> incorporate_primes(M1M2s, _N, []) ->
>    M1M2s;
> incorporate_primes(M1M2s, N, [P|Rest]) ->
>    M1M2s_new = incorporate_prime(M1M2s, N, P),
>    incorporate_primes(M1M2s_new, N, Rest).
>
>
>   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>   %% Richard's improvement.
>   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
>   py3R(N)->
>      [{A,B,C} ||
>          C<- lists:seq(1, N),
>          A<- lists:seq(1, N-C-1),
>          B<- lists:seq(1, N-C-A),
>          A*A + B*B =:= C*C,
>          A+B+C =<  N].
>
>
> %%%%%%%%%%%%%%%%%%%%%  END
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
>
> Cheers,
>
> Ivan.
>
> ----------------------------------------------------------------------
> Do you want to get EVO (ExtendedVisualOtp) to develops client-server
> applicacions using C# / Erlang? Just say it!!!.
>
>
>
> =======================================================================
> Este mensaje ha sido enviado mediante el servicio de correo electrónico  
> que ofrece la Federación de Radioaficionados de Cuba a sus miembros para  
> respaldar el cumplimiento de los objetivos de la organización y su  
> política informativa. La persona que envía este correo asume el  
> compromiso de  usar el servicio a tales fines y cumplir con las  
> regulaciones establecidas.


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/


More information about the erlang-questions mailing list