# Golfed Inverse Ackermann Function [closed]

The following was posted on PPCG:

Your job is to create the slowest growing function you can in no more than 100 bytes.

I did some Googling, and I was interested in the Inverse Ackermann Function:

$$\alpha(m,n) = \min\{i \ge 1 : A(i, \lfloor \frac{m}{n} \rfloor \ge \log_2n\}$$

Where $A$ is the Ackermann Function:

$$A(m,n) = \begin{cases} n + 1, & \text{if} \space m = 0 \\ A(m - 1, 1) & \text{if} \space m > 0 \space \text{and} \space n = 0 \\ A(m - 1, A(m, n - 1)) & \text{if} \space m > 0 \space \text{and} \space n \gt 0 \end{cases}$$

The Ackermann function itself is not too difficult to implement. Here is my implementation:

A=(m,n)=>m?A(m-1,n?A(m,n-1):1):n+1


However, the mathematical stuff in the Inverse Ackermann stumped me. I came up with the following, also changing it from two variables to one:

a=(m,n=m,i=1)=>{while(A(i,m/n|0)<=Math.log2(n))i++;return i}


However, that was yesterday. Today, I'm pretty sure I screwed some stuff up. i will always be one more than it should be, since the loop increments and then checks. So, the code should be this:

a=(m,n=m,i=1)=>{while(A(i,m/n|0)<=Math.log2(n))i++;return i-1}


Now, of course this will StackOverflow very quickly. However, theoretically, it works.

function Ackermann(m, n) {
return m ? Ackermann(m - 1, n ? Ackermann(m, n - 1) : 1) : n + 1;
}

function inverseAckermann(m) {
var n = m;
var i = 1;

while (Ackermann(i, Math.floor(m / n)) <= Math.log2(n)) {
i++;
}

return i - 1;
}


Any improvements to the implementation of the inverse Ackermann would be appreciated. I really wanted to use Math.min but I could not figure how to.

Note: I know this can be golfed more, and I know I can slow it down more. I'm more interested in my algorithm than scoring well in the challenge. Don't worry about keeping your suggestions/improvements golfed either :)

• You are looking for improvements regarding the 'readable' code - such as better style, lower memory usage, better performance? – le_m Jun 9 '17 at 13:10
• @le_m AFAIK the readable code and the golfed code do exactly the same thing, so you can approach either/both, but I assume you will want to mostly touch on the readable ungolfed code. I can remove the golfed code if it is irrelevant. Otherwise you are correct. I'm also interested in if I correctly translated the mathematical formula into code, or if there is a better way to do it. – Stephen S Jun 9 '17 at 13:12
• In the inverseAckermann function, if n = m, m / n always equals 1. I don't see anywhere where n is set. – Artyer Jun 9 '17 at 13:19
• @Artyer Yup, you are correct. I'm not sure I'm interpreting the math correctly - maybe I'm on the wrong stack. I'm really just trying to know how well I converted the formula from Wikipedia to a one-parameter formula. – Stephen S Jun 9 '17 at 13:23
• My bad - i is constrained to be a non-negative integer as it is used as an input to the Ackermann function. – Tamoghna Chowdhury Jun 9 '17 at 13:45

I know that you're supposed to create the slowest-growing function possible, but that doesn't mean you necessarily need to make your function the slowest possible (LoL!).

As far as I can determine, your code for the Ackermann is mathematically correct - according to both Wikipedia and my (admittedly poor) sense of mathematical intuition.

### <BoringMaths>

However, the inverse Ackermann as defined by Wikipedia is supposed to be a two-parameter function, and as such you cannot imitate it using a one-parameter function.

Also, you want a do-while loop here, so that the loop runs at least once even if the constraining condition is false at the start, as well be for my suggestion below. I don't think the return should be i - 1 instead of i either, as you can potentially return 0 if it remains as-is, which is not a legal value.

What you could try, as the ending paragraph of the relevant section of the Wikipedia article mentions, is setting the parameter m to a constant - not n, and especially not making $n=m$ - although that works too.

Here, I'd suggest choosing $m=0$. Such a choice helps with golf-ability - you can get rid of the division and the Math.floor in one fell swoop - $\lfloor\frac{m}{n}\rfloor$ is always $0$, regardless of $n$ (assuming that NaN, when converted to integral type, is 0, as it is in Java). So the loop condition basically becomes $Ack(i, 0) < log_2(n)$. Note the less-than ($\lt$), not less-than-or-equal-to ($\le$): this is the proper negation of the condition greater-than-or-equal-to ($\ge$).

Mathematically, how about a constant function, which is in fact the slowest growing function as it doesn't grow at all? Why not just return a constant and be done with it?

I think the PPCG question's rules forbid submitting a constant function, so let's not dwell on that any more (but it does make for a cheap trick, doesn't it?)

### <NonCritical>

1. Extract out Math.log2(n) into a variable.
2. I think ES6+ gets you let and const - use them instead of var. As far as I remember, the former gets you proper scoping and the latter allows you to declare a named constant. I think my point (1) should have a const declaration.

### Type Coercion is not readable!

Don't use implicit Boolean coercion of numbers in code which you claim to be "readable" - it isn't. Use proper comparisons in readable code, and leave the cool weak-typing hackery for the golfed version. How much does writing out the actual condition improve the readability of the code?

Everything else seems to be fine - naming, indentation, and all.

## Suggested Code:

function Ackermann(m, n) {
if (m < 0 || n < 0) {
throw new TypeError("Arguments to Ackermann must be non-negative");
}
if (m == 0) {
return n + 1;
}
else if (n == 0) {
return Ackermann(m - 1, 1);
} else {
return Ackermann(m - 1, Ackermann(m, n - 1));
}
}

function inverseAckermann(n) {
const log2_n = Math.log2(n);
let i = 0;
// Taking m to be the constant 0 in the definition of the inverse Ackermann function
do {
++i; // Pre-increment implies less side-effects
} while (Ackermann(i, 0) < log2_n);

return i;
}