| Author |
Message |
|
| Guest |
 Posted: Mon Nov 15, 2010 1:08 am |
 |
|
|
Guest
|
| On 13/11/2010, at 8:37 PM, Gilberto Carmenate Garc |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Nov 15, 2010 1:26 am |
|
|
|
Guest
|
On 14/11/2010, at 3:36 AM, Edmond Begumisa wrote:
> Numerical algorithms?
Enumerating pythagorean triples is not a "numerical" algorithm.
It's integer-only, and it doesn't even need large integers.
As far as I know there's nothing in ACML or GSL that would help.
You could call it combinatorics or number theory.
>
>
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Nov 15, 2010 1:31 am |
|
|
|
Guest
|
On 14/11/2010, at 10:17 PM, Hynek Vychodil wrote:
Anyway Erlang is not
> right tool for this job. You should use NIF if performance matter.
Erlang is a fine tool for jobs like this one.
In fact, given its support for large integers,
it is about as good for combinatorial algorithms as
Smalltalk, though perhaps not as good as Lisp.
(But see LFE...)
There is little point in optimising a bad algorithm.
A fairly naive rewrite turns it from O(N**3) into O(N**2).
What really counts here is how easy it is to spot the
algorithmic problem and switch to a better algorithm.
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Nov 15, 2010 3:42 am |
|
|
|
Guest
|
I appreciate that this answer is very insight.
Some discussions before showed that rewriting and rewriting the Erlang code
may beat the speed of the C# program. Some did specific programming
techniques
on aspects of this problem. However, it ought to be that keeping C# program
written in operational semantics the same as the Erlang one. Thus, your
answer is a better one, simple and fair.
On Mon, Nov 15, 2010 at 9:06 AM, Richard O'Keefe <ok@cs.otago.ac.nz> wrote:
>
> On 13/11/2010, at 8:37 PM, Gilberto Carmenate García wrote:
>
> > Hi all!
> > I have been doing tests to Erlang I found this funny stuff that makes
> > Pythagorean Triplets
> >
> > pythag(N) ->
> > [ {A,B,C} ||
> > A <- lists:seq(1,N),
> > B <- lists:seq(1,N),
> > C <- lists:seq(1,N),
> > A+B+C =< N,
> > A*A+B*B =:= C*C].
>
> That's not as efficient as it could be.
>
> C <- lists:seq(1, N),
> A <- lists:seq(1, N-C-1),
> B <- lists:seq(1, N-C-A),
>
> does a factor of 6 or better fewer iterations (tested up to N = 500).
>
>
--
Best Regards.
--- Y-H. H.
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Nov 15, 2010 7:33 am |
|
|
|
Guest
|
I think you can do a wee bit better ...
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].
Since the largest side of the triangle (A) cannot be bigger than Max/2
/Joe
On Mon, Nov 15, 2010 at 2:06 AM, Richard O'Keefe <ok@cs.otago.ac.nz> wrote:
>
> On 13/11/2010, at 8:37 PM, Gilberto Carmenate Garc |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Nov 15, 2010 1:39 pm |
|
|
|
Guest
|
Yes,
I corrected myself later on that.
- Edmond -
On Mon, 15 Nov 2010 12:24:59 +1100, Richard O'Keefe <ok@cs.otago.ac.nz>
wrote:
>
> On 14/11/2010, at 3:36 AM, Edmond Begumisa wrote:
>> Numerical algorithms?
>
> Enumerating pythagorean triples is not a "numerical" algorithm.
> It's integer-only, and it doesn't even need large integers.
> As far as I know there's nothing in ACML or GSL that would help.
> You could call it combinatorics or number theory.
>>
>>
>
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
>
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Nov 15, 2010 1:43 pm |
|
|
|
Guest
|
On Sun, 14 Nov 2010 11:33:25 +1100, Edmond Begumisa
<ebegumisa@hysteria-tech.com> wrote:
> ... When you look closer, the bottleneck with all the solutions so far
> isn't the calculation itself (I was wrong about that earlier) -- it's
> actually the permutation (the part done with accumulators/generators) ...
- Edmond -
On Mon, 15 Nov 2010 12:24:59 +1100, Richard O'Keefe <ok@cs.otago.ac.nz>
wrote:
>
> On 14/11/2010, at 3:36 AM, Edmond Begumisa wrote:
>> Numerical algorithms?
>
> Enumerating pythagorean triples is not a "numerical" algorithm.
> It's integer-only, and it doesn't even need large integers.
> As far as I know there's nothing in ACML or GSL that would help.
> You could call it combinatorics or number theory.
>>
>>
>
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
>
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Nov 15, 2010 2:18 pm |
|
|
|
Guest
|
On Mon, 15 Nov 2010 04:26:12 +1100, Toby Thain <toby@telegraphics.com.au>
wrote:
> What were these great sacrifices? Pointers?
>
> --Toby
http://www.erlang.org/faq/introduction.html#id49850
But yeah, "trade-offs" would have been a better term than "sacrifices".
- Edmond -
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Nov 15, 2010 3:04 pm |
|
|
|
Guest
|
Hello Richard,
I have a question...
> Erlang is a fine tool for jobs like this one.
Interesting... I would have never thought this. I would have instinctively
reached for a language with mutable memory, thinking that this would make
the most sense for combinatorial* work (I don't know this for fact, and I
could be very wrong, but that's what instinct would tell me.) But then,
I'm relatively new to Erlang.
* I've been calling this permutation but I don't know if that's accurate.
> There is little point in optimising a bad algorithm.
Well put. But say you have an 'ok' algorithm. Not the best, but not
blatantly flawed either.
I think of optimisation as something you put on a version 2 to-do list.
Optimisation to me means staring hard at code and trying to figure out
ways to get it to perform better (faster, less memory, less CPU time,
etc). This normally means re-writing code that's easy to follow into code
that's no-so-easy to follow. Mind you, for Erlang, I don't look at
parallelising as optimisation as others seem to. To me, it's just a
building block made available and normally it can be applied without
changing an algo too much (I'd say it's not used enough).
Of all the variations presented so far, IMO, Garcia's first is the easiest
to follow (ignoring that obvious flaw with the repeated list:seq call). A
non-mathematical mind like myself can see exactly what he's trying to do.
The others (including the ones from Willem and Tony that I tried to
parallelise), seem harder to follow. Maybe that's coz they are optimised
versions. The authors could have stared long and hard.
So my question is: if version 1 isn't performing "reasonably" acceptably
for Garcia's purpose, and version 1 isn't blatantly flawed. Isn't this a
strong indicator that he's using the wrong tool?
- Edmond -
On Mon, 15 Nov 2010 12:29:49 +1100, Richard O'Keefe <ok@cs.otago.ac.nz>
wrote:
>
> On 14/11/2010, at 10:17 PM, Hynek Vychodil wrote:
> Anyway Erlang is not
>> right tool for this job. You should use NIF if performance matter.
>
> Erlang is a fine tool for jobs like this one.
> In fact, given its support for large integers,
> it is about as good for combinatorial algorithms as
> Smalltalk, though perhaps not as good as Lisp.
> (But see LFE...)
>
> There is little point in optimising a bad algorithm.
> A fairly naive rewrite turns it from O(N**3) into O(N**2).
> What really counts here is how easy it is to spot the
> algorithmic problem and switch to a better algorithm.
>
>
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
>
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| MononcQc |
| Posted: Mon Nov 15, 2010 3:23 pm |
|
|
|
User
Joined: 14 Aug 2009
Posts: 37
Location: Quebec, Canada
|
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?"
If 90% of your calls fall in the same range, you might as well just cache
the results and speed up 90% of the computations. No optimization required.
Then to reduce the overhead of the rest and maybe make the whole set of
queries more predictable, you could use Morgen's algorithm with a static or
a cached sieve table/incorporated primes for the edge cases, or allow the
algorithm to resume from the one you stored, etc.
There are many practical solutions that can require far less work than
rewriting the algorithm, making it harder to read. Understand the problem
before finding its solution.
On Mon, Nov 15, 2010 at 10:02 AM, Edmond Begumisa <
ebegumisa@hysteria-tech.com> wrote:
>
> I think of optimisation as something you put on a version 2 to-do list.
> Optimisation to me means staring hard at code and trying to figure out ways
> to get it to perform better (faster, less memory, less CPU time, etc). This
> normally means re-writing code that's easy to follow into code that's
> no-so-easy to follow. Mind you, for Erlang, I don't look at parallelising as
> optimisation as others seem to. To me, it's just a building block made
> available and normally it can be applied without changing an algo too much
> (I'd say it's not used enough).
>
Post received from mailinglist |
|
|
| Back to top |
 
|
| Guest |
| Posted: Mon Nov 15, 2010 3:29 pm |
|
|
|
Guest
|
Small Correction...
> Of all the variations presented so far, IMO, Garcia's first is the
> easiest to follow
They've been since some variations of this that are equally easy to follow
and try to eliminate small but important flaws (including yours). The
one's that try to use functions instead of list combination generators for
the combinatorial part are the ones I have trouble reading. But that may
just be me.
- Edmond -
On Tue, 16 Nov 2010 02:02:50 +1100, Edmond Begumisa
<ebegumisa@hysteria-tech.com> wrote:
> Hello Richard,
>
> I have a question...
>
>> Erlang is a fine tool for jobs like this one.
>
> Interesting... I would have never thought this. I would have
> instinctively reached for a language with mutable memory, thinking that
> this would make the most sense for combinatorial* work (I don't know
> this for fact, and I could be very wrong, but that's what instinct would
> tell me.) But then, I'm relatively new to Erlang.
>
> * I've been calling this permutation but I don't know if that's accurate.
>
>> There is little point in optimising a bad algorithm.
>
> Well put. But say you have an 'ok' algorithm. Not the best, but not
> blatantly flawed either.
>
> I think of optimisation as something you put on a version 2 to-do list.
> Optimisation to me means staring hard at code and trying to figure out
> ways to get it to perform better (faster, less memory, less CPU time,
> etc). This normally means re-writing code that's easy to follow into
> code that's no-so-easy to follow. Mind you, for Erlang, I don't look at
> parallelising as optimisation as others seem to. To me, it's just a
> building block made available and normally it can be applied without
> changing an algo too much (I'd say it's not used enough).
>
> Of all the variations presented so far, IMO, Garcia's first is the
> easiest to follow (ignoring that obvious flaw with the repeated list:seq
> call). A non-mathematical mind like myself can see exactly what he's
> trying to do. The others (including the ones from Willem and Tony that I
> tried to parallelise), seem harder to follow. Maybe that's coz they are
> optimised versions. The authors could have stared long and hard.
>
> So my question is: if version 1 isn't performing "reasonably" acceptably
> for Garcia's purpose, and version 1 isn't blatantly flawed. Isn't this a
> strong indicator that he's using the wrong tool?
>
> - Edmond -
>
> On Mon, 15 Nov 2010 12:29:49 +1100, Richard O'Keefe <ok@cs.otago.ac.nz>
> wrote:
>
>>
>> On 14/11/2010, at 10:17 PM, Hynek Vychodil wrote:
>> Anyway Erlang is not
>>> right tool for this job. You should use NIF if performance matter.
>>
>> Erlang is a fine tool for jobs like this one.
>> In fact, given its support for large integers,
>> it is about as good for combinatorial algorithms as
>> Smalltalk, though perhaps not as good as Lisp.
>> (But see LFE...)
>>
>> There is little point in optimising a bad algorithm.
>> A fairly naive rewrite turns it from O(N**3) into O(N**2).
>> What really counts here is how easy it is to spot the
>> algorithmic problem and switch to a better algorithm.
>>
>>
>>
>> ________________________________________________________________
>> erlang-questions (at) erlang.org mailing list.
>> See http://www.erlang.org/faq.html
>> To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
>>
>
>
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Nov 15, 2010 3:54 pm |
|
|
|
Guest
|
On Tue, 16 Nov 2010 02:21:44 +1100, Fred Hebert <mononcqc@gmail.com> wrote:
>
> If 90% of your calls fall in the same range, you might as well just cache
> the results and speed up 90% of the computations. No optimization
> required.
> Then to reduce the overhead of the rest and maybe make the whole set of
> queries more predictable, you could use Morgen's algorithm with a static
> or
> a cached sieve table/incorporated primes for the edge cases, or allow the
> algorithm to resume from the one you stored, etc.
I thought about doing something like that. I tried to write some code my
side with using an ets table but at the end of the day got no speed ups
coz ets:insert had to be called as I populated the cache. I suspect it
might be that the table had to keep growing. I haven't used ets much -- is
there a way of creating an empty table of certain size in one go?
- Edmond -
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Nov 15, 2010 9:14 pm |
|
|
|
Guest
|
Richard...
> So my question is: if version 1 isn't performing "reasonably" acceptably
> for Garcia's purpose, and version 1 isn't blatantly flawed. Isn't this a
> strong indicator that he's using the wrong tool?
>
You can probably ignore that last question now. I've answered my own
question after taking a closer look at other solutions!
- Edmond -
On Tue, 16 Nov 2010 02:02:50 +1100, Edmond Begumisa
<ebegumisa@hysteria-tech.com> wrote:
> Hello Richard,
>
> I have a question...
>
>> Erlang is a fine tool for jobs like this one.
>
> Interesting... I would have never thought this. I would have
> instinctively reached for a language with mutable memory, thinking that
> this would make the most sense for combinatorial* work (I don't know
> this for fact, and I could be very wrong, but that's what instinct would
> tell me.) But then, I'm relatively new to Erlang.
>
> * I've been calling this permutation but I don't know if that's accurate.
>
>> There is little point in optimising a bad algorithm.
>
> Well put. But say you have an 'ok' algorithm. Not the best, but not
> blatantly flawed either.
>
> I think of optimisation as something you put on a version 2 to-do list.
> Optimisation to me means staring hard at code and trying to figure out
> ways to get it to perform better (faster, less memory, less CPU time,
> etc). This normally means re-writing code that's easy to follow into
> code that's no-so-easy to follow. Mind you, for Erlang, I don't look at
> parallelising as optimisation as others seem to. To me, it's just a
> building block made available and normally it can be applied without
> changing an algo too much (I'd say it's not used enough).
>
> Of all the variations presented so far, IMO, Garcia's first is the
> easiest to follow (ignoring that obvious flaw with the repeated list:seq
> call). A non-mathematical mind like myself can see exactly what he's
> trying to do. The others (including the ones from Willem and Tony that I
> tried to parallelise), seem harder to follow. Maybe that's coz they are
> optimised versions. The authors could have stared long and hard.
>
> So my question is: if version 1 isn't performing "reasonably" acceptably
> for Garcia's purpose, and version 1 isn't blatantly flawed. Isn't this a
> strong indicator that he's using the wrong tool?
>
> - Edmond -
>
> On Mon, 15 Nov 2010 12:29:49 +1100, Richard O'Keefe <ok@cs.otago.ac.nz>
> wrote:
>
>>
>> On 14/11/2010, at 10:17 PM, Hynek Vychodil wrote:
>> Anyway Erlang is not
>>> right tool for this job. You should use NIF if performance matter.
>>
>> Erlang is a fine tool for jobs like this one.
>> In fact, given its support for large integers,
>> it is about as good for combinatorial algorithms as
>> Smalltalk, though perhaps not as good as Lisp.
>> (But see LFE...)
>>
>> There is little point in optimising a bad algorithm.
>> A fairly naive rewrite turns it from O(N**3) into O(N**2).
>> What really counts here is how easy it is to spot the
>> algorithmic problem and switch to a better algorithm.
>>
>>
>>
>> ________________________________________________________________
>> erlang-questions (at) erlang.org mailing list.
>> See http://www.erlang.org/faq.html
>> To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
>>
>
>
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Nov 15, 2010 9:30 pm |
|
|
|
Guest
|
On Mon, Nov 15, 2010 at 4:21 PM, Fred Hebert <mononcqc@gmail.com> 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 
--
J.
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Nov 15, 2010 9:53 pm |
|
|
|
Guest
|
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, , 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@gmail.com> 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@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
|
|
All times are GMT
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
|
|
|
Digg It
Del.icio.us
Reddit
Facebook
Stumble Upon
Technorati
