6
\$\begingroup\$

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.

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)) <= 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 :)

\$\endgroup\$

closed as off-topic by Mike Brant, t3chb0t, Simon Forsberg Jun 10 '17 at 11:49

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Mike Brant, t3chb0t, Simon Forsberg
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ You are looking for improvements regarding the 'readable' code - such as better style, lower memory usage, better performance? \$\endgroup\$ – le_m Jun 9 '17 at 13:10
  • \$\begingroup\$ @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. \$\endgroup\$ – Stephen S Jun 9 '17 at 13:12
  • 1
    \$\begingroup\$ In the inverseAckermann function, if n = m, m / n always equals 1. I don't see anywhere where n is set. \$\endgroup\$ – Artyer Jun 9 '17 at 13:19
  • \$\begingroup\$ @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. \$\endgroup\$ – Stephen S Jun 9 '17 at 13:23
  • 1
    \$\begingroup\$ My bad - i is constrained to be a non-negative integer as it is used as an input to the Ackermann function. \$\endgroup\$ – Tamoghna Chowdhury Jun 9 '17 at 13:45
1
\$\begingroup\$

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?)

</BoringMaths>

<NonCritical>

A few small improvements for your implementation in the readable version

  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.

</NonCritical>

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;
}
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.