LAST RESUME of Pytagoriam Numbers!!!

Ivan Carmenates García <>
Sun Jan 15 05:11:42 CET 2006


Compiled using c(py) normal in the shell.

Feel free to make a new Resume on a DualCore CPU!!!


Now we are re-talking about!!!

Tested on Intel(R) Celeron CPU 2.13 GHz, 192 of Ram

*** Pytagoriam's Numbers REPORT! ***

Using N = 300

*** THE ORIGINAL IMPLEMENTATIONS (ME!)****
-py1:         14860000 mcs = 14.86 s
-py2:         14843999 mcs = 14.843999 s
-py3:         12749999 mcs = 12.749999 s

*** Tony's implementations ****
-pythag1:     11702999 mcs = 11.702999 s
-pythag2:     1983999 mcs = 1.983999 s

*** Hynek's implementation ****
Simpler and about 5% faster version
-pythag3:     1952999 mcs = 1.952999 s

*** Edmond's implementation, using parallelism****
-py2E:        14843999 mcs = 14.843999 s

*** Willem's implementation****
-wpythag2:    1749999 mcs = 1.749999 s

*** Hynek's new implementation****
-pythag4:     1140999 mcs = 1.140999 s

*** Willem's new implementation in parallel by Edmond!!!****
-wpythag2P:   1795999 mcs = 1.795999 s

*** Morten's implementation****
-pythag5:     46999 mcs = 0.046999 s

*** Richard's improvement****
-py3R:        46999 mcs = 0.046999 s   *** NEW ***

*** Joe's improvement****
-py3a:        1577999 mcs = 1.577999 s    *** NEW ***

Comparisons in results agains 'pythag1' Tony's
function
py1 returns the same than 'pythag1'
py2 returns the same than 'pythag1'
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 returns the same than 'pythag1'
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 returns the same than 'pythag1' <- now are we talking about!!! (is 
the best!!!)
py3a returns the same than 'pythag1'

NOTE: Time took using timer:tc/3 function.


%*******************   START CODE *********************

-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 Edmond.
     {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]),

     %% Joe's improvement.
     {T13,R13} = timer:tc(py,py3a,[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 
Edmond!!!****~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("~n*** Joe's improvement****~n"),
     io:format("-py3a:        ~p mcs = ~p s~n", [T13,T13/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},
           {py3a,R13}],
     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)->
     lists:reverse(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} ||
         A <- lists:seq(1, N div 2),
         B <- lists:seq(1, N - A),
         C <- [trunc(math:sqrt(A * A + B * B))],
         A + B + C =< N,
         A*A + B*B =:= C*C].

  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %% Joe's improvement.
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
py3a(Max) ->
     N = Max div 2,
     [{A,B,C} ||
    A <- lists:seq(1,N+1),
    B <- lists:seq(1,Max-A),
    C <- lists:seq(1,Max-A-B),
    A*A + B*B =:= C*C].

%************************* END CODE*************************

Cheers,

Ivan.


=======================================================================
Este mensaje ha sido enviado mediante el servicio de correo electronico 
que ofrece la Federacion de Radioaficionados de Cuba a sus miembros para 
respaldar el cumplimiento de los objetivos de la organizacion y su 
politica informativa. La persona que envia este correo asume el 
compromiso de  usar el servicio a tales fines y cumplir con las 
regulaciones establecidas.


=======================================================================
Este mensaje ha sido enviado mediante el servicio de correo electronico 
que ofrece la Federacion de Radioaficionados de Cuba a sus miembros para 
respaldar el cumplimiento de los objetivos de la organizacion y su 
politica informativa. La persona que envia este correo asume el 
compromiso de  usar el servicio a tales fines y cumplir con las 
regulaciones establecidas.



More information about the erlang-questions mailing list