[Shootout-list] Ackermann

[John Skaller]

On Sat, 2005-06-18 at 11:18 +0300, Einar Karttunen wrote:
> John Skaller <skaller@users.sourceforge.net> writes:
> > Real partial evaluators don't *allow* you to
> > distinguish which phase code runs in.
> 
> Then how about taking both N and M from the command line?
> That should solve things if we want to play that game.

That is the right idea. I am not sure this is enough
for Ackermann, that is, whether it introduces sufficient
feasible outcomes to enforce the desire: perhaps
someone can tell the size of the set

S = { (m, n) | time (ack(m,n)) < time_limit }

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.

Somehow I doubt |S| will be larger than that.

So the solution has to be to throw out ackermann.
For a math function:

(a) use floating point, or
(b) have a minimum of 3 integer parameters

This prevents the test being abused by simply
precomputing an array.

-- 
John Skaller <skaller at users dot sf dot net>
Download Felix: http://felix.sf.net