[erlang-questions] Erlang shows its slow face!

[Morten Krogh]

And a solution that uses the fact that A and B can not both be odd.

py6R(N)->
   EvenA = lists:flatten([[{A,B,C}, {B,A,C}] ||
   A <- lists:seq(2, N div 2, 2),
   B <- lists:seq(A + 1, max(A, N*(N-2*A) div (2*(N-A)))),
   C <- [trunc(math:sqrt(A * A + B * B))],
         A + B + C =< N,
   A*A + B*B =:= C*C]),
   OddA = lists:flatten([[{A,B,C}, {B,A,C}] ||
   A <- lists:seq(1, N div 2, 2),
   B <- lists:seq(A + 1, max(A, N*(N-2*A) div (2*(N-A))), 2),
   C <- [trunc(math:sqrt(A * A + B * B))],
         A + B + C =< N,
   A*A + B*B =:= C*C]),
   lists:sort(EvenA ++ OddA).

Morten.




On 11/15/10 10:51 PM, Morten Krogh wrote:
> Hi again,
>
> The py3R can be made to have a much better check on the bounds of the 
> lists.
> Also, you should use that the triples are symmetric so {A,B,C} can be 
> replaced with {B,A,C}.
>
> py5R(N)->
>     lists:sort(lists:flatten([[{A,B,C}, {B,A,C}] ||
>     A <- lists:seq(1, N div 2),
>      B <- lists:seq(A + 1, max(A, N*(N-2*A) div (2*(N-A)))),
>      C <- [trunc(math:sqrt(A * A + B * B))],
>              A + B + C =< N,
>      A*A + B*B =:= C*C])).
>
>
>
> the max(..,..) is really stupid, but I learnt something new about 
> erlang, namely that
>
> lists:seq(10,8), for example, produces an exception, whereas 
> lists:seq(10,9) = []
>
> if lists:seq(A,B) = [] for A > B, the max above could have been removed.
>
> Morten.
>
>
> On 11/15/10 10:28 PM, Jesper Louis Andersen wrote:
>> On Mon, Nov 15, 2010 at 4:21 PM, Fred Hebert<mononcqc@REDACTED>  wrote:
>>> I think the first thing to do before optimizing is understanding how 
>>> you use
>>> the data. In the case of Pythagorean triplets like these, the right 
>>> question
>>> might as well be "how many triplets do I need? What values do I need 
>>> to work
>>> with?"
>> Let me add:
>>
>> Optimization is many things. One of the tenets are how easy it is to
>> change your implementation, facing new knowledge. If you look at some
>> of the optimized variants, it should be fairly obvious that many of
>> them provide impressive speedups (for large N) with very few changes
>> to the original code as soon as an observation has been made.
>>
>> My experience is that C, C++ or Java tend to require much more work
>> for these iterations. It turns out there is more to fast code than
>> just having a language isomorphic to assembly :)
>>
>
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@REDACTED
>