Stack Space & Ackermann

[H. S. Teoh via Digitalmars-d-learn]

On Thu, Jan 05, 2017 at 04:50:19AM +0000, Era Scarecrow via Digitalmars-d-learn wrote:
> Well re-watched a video regarding the Ackermann function which is a
> heavily recursive code which may or may not ever give a result in our
> lifetimes.  However relying on the power of memoize I quickly find
> that when the program dies (from 5 minutes or so) nearly instantly
> (and only using 9Mb of memory).
> 
> long ack(long m, long n) {
>     long ans;
> 
>     if (m == 0) ans = n + 1;
>     else if (n==0) ans = ack(m-1, 1);
> //    else ans = ack(m-1, ack(m, n-1)); // original
>     else ans = memoize!ack(m-1, memoize!ack(m, n-1));
> 
>     return ans;
> }
> 
> This is only due to the limited stackframe space.
[...]

For heavily-recursive functions like this one, you *really* want to be
revising the algorithm so that it *doesn't* recurse on the runtime
stack.  Keep in mind that the Ackermann function was originally
conceived specifically to prove that a certain elementary class of
recursive functions (called "primitive recursive" functions) cannot
perform certain computations. Very roughly speaking, primitive recursive
functions are "well-behaved" with regard to recursion depth; so the
Ackermann function was basically *designed* to have very bad
(unrestricted) recursion depth such that no primitive recursive function
could possibly catch up to it. Translated to practical terms, this means
that your runtime stack is pretty much guaranteed to overflow except for
the most trivial values of the function.

The other problem with your code, as written, is that it will quickly
and easily overflow any fixed-width integer such as long here. For
example, ack(4,1) == 65533, but ack(4,2) is a value that requires 65536
bits to represent (i.e., an integer that's 1 KB in size), and ack(4,3)
is a value that requires ack(4,2) bits to represent, i.e., the number of
bits required is a number so huge that it itself requires 1KB to
represent. This far exceeds any memory capacity of any computer system
in existence today, and we haven't even gotten to ack(4,4) yet.

You might at least be able to get to ack(4,2) if you use BigInt instead
of long (though be prepared for incredibly huge running times before the
answer ever appears!), but even BigInt won't help you once you get to
ack(4,3) and beyond.  And don't even think about ack(5,n) for any value
of n greater than 0, because those values are so ridiculously huge you
need special notation just to be able to write them down at all.

Because of this, your code as written most definitely does *not* compute
the Ackermann function except for the smallest arguments, because once
ack(m, n-1) overflows long, it can only return the answer module
long.max, which will be much smaller than the actual value, so the
nested recursion ack(m-1, ack(n, m-1)) actually will compute a value far
smaller than what the real Ackermann function would (and it would run
much faster than the real Ackermann function).

Not to mention, the recursive definition of the Ackermann function is
really bad for actually computing its values in a computer, because it
makes a huge number of recursive calls just to compute something as
simple as + and * (essentially what ack(1,n) and ack(2,n) do). In a
practical implementation you'd probably want to special case these
arguments to use faster, non-recursive code paths.  Using memoize
alleviates the problem somewhat, but it could be improved more.

Nonetheless, even if you optimize said code paths, you still won't be
able to get any sane results for m>4 or anything beyond the first few
values for m=4. The Ackermann function is *supposed* to be
computationally intractible -- that's what it was designed for. :-P


T

-- 
Do not reason with the unreasonable; you lose by definition.