[Shootout-list] Rule 30
Robert Seeger
Robert Seeger <rhseeger@gmail.com>
Fri, 20 May 2005 08:07:02 -0400
------=_Part_1633_2861475.1116590822511
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
On 5/19/05, Jon Harrop <jon@ffconsultancy.com> wrote:
>=20
> On Thursday 19 May 2005 20:44, Robert Seeger wrote:
> > On 5/19/05, Jon Harrop <jon@ffconsultancy.com> wrote:
> > > We're trying to measure how long it took to compute.
> >
> > True... However, I think the point is that actually doing the=20
> computation
> > can be a condition of the test.
>=20
> No it can't. That condition cannot be enforced in practice for many=20
> languages
> in the shootout. This is precisely why Haskell programmers have trouble=
=20
> with
> poorly designed benchmarks.
I call bunk. Haskell can be told "what to do". The issue lies in tests that=
=20
try to tell you the steps to take to do it. It's perfectly acceptable to sa=
y=20
"calculate f(x) =3D f(x-1) + f(x-2) for a any specified x" in a test=20
description.If the programmer adds in recomputed values, then the program=
=20
isn't "calculating" it, and is invalid. The problem is in coming up with=20
such algorithms that avoid memoization and the like.
> Just because it CAN be precomputed doesn't mean it HAS to be.
>=20
> Yes, precisely.
>=20
> Some implementations may precompute it without the reader's knowledge.=20
> More
> worryingly, some language implementations may precompute it without the
> author's knowledge. This helps nobody as, in real life, we don't spend a=
=20
> lot
> of time executing programs to repeatedly compute the same constant.
>=20
> Skaller's idea of designing tasks which require a suitably large number o=
f
> possible inputs to practically obviate precomputation is the ideal=20
> solution.
> As I have said, this does not require much data to be loaded. Computing=
=20
> the
> center bit after n iterations of Wolfram's rule 30 from a given seed is a=
n
> ideal example of this, IMHO.
Sure, having the test definition say "compute" it is fine. This may be a=20
fine example of an algorithm that (generally) defies memoization.
Rob Seeger
------=_Part_1633_2861475.1116590822511
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
<br><br><div><span class=3D"gmail_quote">On 5/19/05, <b class=3D"gmail_send=
ername">Jon Harrop</b> <<a href=3D"mailto:jon@ffconsultancy.com">jon@ffc=
onsultancy.com</a>> wrote:</span><blockquote class=3D"gmail_quote" style=
=3D"border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; p=
adding-left: 1ex;">
On Thursday 19 May 2005 20:44, Robert Seeger wrote:<br>> On 5/19/05, Jon=
Harrop <<a href=3D"mailto:jon@ffconsultancy.com">jon@ffconsultancy.com<=
/a>> wrote:<br>> > We're trying to measure how long it took to com=
pute.
<br>><br>> True... However, I think the point is that actually doing =
the computation<br>> can be a condition of the test.<br><br>No it can't.=
That condition cannot be enforced in practice for many languages<br>in the=
shootout. This is precisely why Haskell programmers have trouble with
<br>poorly designed benchmarks.</blockquote><div><br>
I call bunk. Haskell can be told "what to do". The issue lies in =
tests
that try to tell you the steps to take to do it. It's perfectly
acceptable to say "calculate f(x) =3D f(x-1) + f(x-2) for a any specif=
ied
x" in a test description.If the programmer adds in recomputed values,
then the program isn't "calculating" it, and is invalid. The prob=
lem is
in coming up with such algorithms that avoid memoization and the like.<br>
</div><br><blockquote class=3D"gmail_quote" style=3D"border-left: 1px=
solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">&=
gt; Just because it CAN be precomputed doesn't mean it HAS to be.<br><br>Ye=
s, precisely.
<br><br>Some implementations may precompute it without the reader's knowled=
ge. More<br>worryingly, some language implementations may precompute it wit=
hout the<br>author's knowledge. This helps nobody as, in real life, we don'=
t spend a lot
<br>of time executing programs to repeatedly compute the same constant.<br>=
<br>Skaller's idea of designing tasks which require a suitably large number=
of<br>possible inputs to practically obviate precomputation is the ideal s=
olution.
<br>As I have said, this does not require much data to be loaded. Computing=
the<br>center bit after n iterations of Wolfram's rule 30 from a given see=
d is an<br>ideal example of this, IMHO.</blockquote><div><br>
Sure, having the test definition say "compute" it is fine. This m=
ay be
a fine example of an algorithm that (generally) defies memoization.<br>
<br>
Rob Seeger<br>
</div><br></div><br>
------=_Part_1633_2861475.1116590822511--