Golfed Inverse Ackermann Function 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, &amp; \text{if} \space m = 0 \\
A(m - 1, 1) &amp; \text{if} \space m &gt; 0 \space \text{and} \space n = 0 \\
A(m - 1, A(m, n - 1)) &amp; \text{if} \space m &gt; 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)=&gt;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)=&gt;{while(A(i,m/n|0)&lt;=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)=&gt;{while(A(i,m/n|0)&lt;=Math.log2(n))i++;return i-1}


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

Readable:

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)) &lt;= 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 :)
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.

&lt;BoringMaths&gt;

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) &lt; 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?)

&lt;/BoringMaths&gt;

&lt;NonCritical&gt;

A few small improvements for your implementation in the readable version


Extract out Math.log2(n) into a variable.
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.

&lt;/NonCritical&gt;

Suggested Code:

function Ackermann(m, n) {
  if (m &lt; 0 || n &lt; 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) &lt; log2_n); 

  return i;
}