Ackermann Function - Use As Benchmark

Use As Benchmark

The Ackermann function, due to its definition in terms of extremely deep recursion, can be used as a benchmark of a compiler's ability to optimize recursion. The first use of Ackermann's function in this way was by Yngve Sundblad, The Ackermann function. A Theoretical, computational and formula manipulative study. (BIT 11 (1971), 107119).

This seminal paper was taken up by Brian Wichmann (co-author of the Whetstone benchmark) in a trilogy of papers written between 1975 and 1982.

For example, a compiler which, in analyzing the computation of A(3, 30), is able to save intermediate values like A(3, n) and A(2, n) in that calculation rather than recomputing them, can speed up computation of A(3, 30) by a factor of hundreds of thousands. Also, if A(2, n) is computed directly rather than as a recursive expansion of the form A(1, A(1, A(1,...A(1, 0)...))), this will save significant amounts of time. Computing A(1, n) takes linear time in n. Computing A(2, n) requires quadratic time, since it expands to O(n) nested calls to A(1, i) for various i. Computing A(3, n) requires time proportionate to 4n+1. The computation of A(3, 1) in the example above takes 16 (42) steps.

A(4, 2) cannot possibly be computed by simple recursive application of the Ackermann function in any tractable amount of time. Instead, shortcut formulas such as A(3, n) = 8×2n−3 are used as an optimization to complete some of the recursive calls.

A practical method of computing functions similar to Ackermann's is to use memoization of intermediate results. A compiler could apply this technique to a function automatically using Donald Michie's "memo functions".