[Shootout-list] Ackermann

[Jon Harrop]

On Saturday 18 June 2005 09:58, you wrote:
> John Skaller <skaller@users.sourceforge.net> writes:
> > We need |S| to be larger than an array which can
> > practically fit into memory. We know in advance
> > that we can easily fit a 65K * 65K array into
> > a large machine, that is, it isn't that hard
> > to have enough virtual memory to support 32 bits
> > of indexing.

This is irrelevant. You don't need to precompute all values of Ackermann, you 
just need to precompute a single, strategically chosen value and your program 
will be vastly faster. So the extra compile time and memory usage will be 
immeasurably small - we can't even detect when this has been done!

> Is there any compiler in the shootout which does this?

Implementations can do this. I can spot when the C++ one does. I can't spot 
when the Scheme or Haskell ones do. I know many other tests have cheated the 
subjective rules placed upon them. I'm not happy to just fix them because I'm 
confident that I've missed many others. It would be much better to just fix 
the tests themselves.

> As for most realworld apps this behaviour is not desirable as
> automatic...

Yes, authors have to knowingly do this, and they do.

> > So the solution has to be to throw out ackermann.

Yes.

> Please no. Ackerman is a simple test easy to implement in any language.

There are plenty of other simple tests.

> It works by using a simple rule "don't try to cheat".
> Is that really too hard?

Yes, that really is too hard. This is exactly what I keep saying - the notion 
of "cheat" is totally subjective. The only solutions is to be design the 
tests such that no arbitrary restrictions are required to make them 
worthwhile. Note that this isn't even difficult, it's just that people have 
to recognise its value.

> > For a math function:
> >
> > (a) use floating point, or

No, this is just a work around for C++ templates allowing int but not float. 
We just need to allow a large number of possible inputs to all tests.

> One can precompute for interesting floating point values too ;)
> Like precompute answer for all floating point numbers representable as a
> string shorter than X ;)
>
> Also many programmers couldn't care less about FP performance. In my
> real application I don't have any performance critical FP code, but have
> many times integer code which is performance critical.

I agree.

> > (b) have a minimum of 3 integer parameters

What's wrong with 1 integer value?

> > This prevents the test being abused by simply
> > precomputing an array.
>
> One of the good sides of the shootout was to use simple problems for the
> benchmarking. Simple problems by nature can be precomputed.

That is not true. For example, Rule 30 is simple and it can't be precomputed.

> I think that 
> enforcing "don't precompute it" is simpler than using more complex
> problems.

We're not advocating using more complex problems, just using better designed 
problems. I agree entirely that there should be a spread of problems from 
easy to complicated.

Consider this: if "random" seeded the random number generator with the given 
integer then the test would not be any more "complex" but could no longer be 
precomputed.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists