Advent Calendar 2020

| Day 19 | Day 20 | Day 21 |

The gift is presented by Yozen Hernandez. Today he is talking about his solution to the task Ackermann function of “The Weekly Challenge - 017”. This is re-produced for Advent Calendar 2020 from the original post by Yozen Hernandez.

The Weekly Challenge is back, and our first challenge was to implement a function known as the Ackermann function:

Create a script to demonstrate Ackermann function. The Ackermann function is defined as below, m and n are positive number:

A(m, n) = n + 1 if m = 0 A(m, n) = A(m - 1, 1) if m > 0 and n = 0 A(m, n) = A(m - 1, A(m, n - 1)) if m > 0 and n > 0

Technically, the above formulation is known as the “Ackermann-Péter function”, but as the Wikipedia page states, many authors refer to it as “the” Ackermann function.

This is looked like a fairly straightforward implementation of a recursive function, but it did have a few hairs. Firstly, as can be seen above, the function is piecewise, and is defined only for non-negative integers. In fact, the recursive calls gradually step the values down to 0, with the deepest call possible being reached when m=0.

sub A ( $m = 3, $n = 3) {
    croak "Error: function only defined for nonnegative integers."
        . "(got: m = $m, n = $n)"
        if ( $m < 0 && $n < 0 );

    # A(m, n) = n + 1                  if m = 0
    return $n + 1 if $m == 0;

    # A(m, n) = A(m - 1, 1)            if m > 0 and n = 0
    # A(m, n) = A(m - 1, A(m, n - 1))  if m > 0 and n > 0
    return A( $m - 1, ($n == 0) ? 1 : A($m, $n-1) );
}

One thing I initially missed when implementing this, is that the function not only should subtract 1 from $n when both values are greater than 0, but it should actually make a second, embedded call there! It took me forever to notice that was missing 😒.

Once that was implemented, I decided to test it with larger values, because I don’t read whole Wikipedia pages. After about a minute of waiting, I decided to scoll down… You should check out the table of values on the wiki page. The short version is that the Ackermann function grows. VERY quickly. I kept my testing down to some smaller values, and those all passed.

Finally, I decided to compare performance with and without memoization. Memoizing really only makes sense with repeated execution, and I don’t know of the actual applications of this function so I don’t know how true that would be.

With default parameters, using Benchmark::Forking gets me the following results;

        Rate        no_memo    memo
no_memo 269501/s    --         -68%
memo    850801/s    216%       --

Its a definite improvement, but again, I’m not sure how useful it would be in a real world application.

If you have any suggestion then please do share with us perlweeklychallenge@yahoo.com.

Advent Calendar 2020