39
\$\begingroup\$

The Ackermann function is notable for being the one of the simplest examples of a total, computable function that isn't primitive recursive.

We will use the definition of A(m,n) taking in two nonnegative integers where

A(0,n) = n+1
A(m,0) = A(m-1,1)
A(m,n) = A(m-1,A(m,n-1))

You may implement

  • a named or anonymous function taking two integers as input, returning an integer, or
  • a program taking two space- or newline-separated integers on STDIN, printing a result to STDOUT.

You may not use an Ackermann function or hyperexponentiation function from a library, if one exists, but you may use any other function from any other library. Regular exponentiation is allowed.

Your function must be able to find the value of A(m,n) for m ≤ 3 and n ≤ 10 in less than a minute. It must at least theoretically terminate on any other inputs: given infinite stack space, a native Bigint type, and an arbitrarily long period of time, it would return the answer. Edit: If your language has a default recursion depth that is too restrictive, you may reconfigure that at no character cost.

The submission with the shortest number of characters wins.

Here are some values, to check your answer:

  A  | n=0     1     2     3     4     5     6     7     8     9    10
-----+-----------------------------------------------------------------
 m=0 |   1     2     3     4     5     6     7     8     9    10    11
   1 |   2     3     4     5     6     7     8     9    10    11    12
   2 |   3     5     7     9    11    13    15    17    19    21    23
   3 |   5    13    29    61   125   253   509  1021  2045  4093  8189
   4 |  13 65533   big   really big...
\$\endgroup\$
8
  • 15
    \$\begingroup\$ How has this not been asked before?? \$\endgroup\$ – Calvin's Hobbies Oct 22 '14 at 4:56
  • 9
    \$\begingroup\$ I think it'd be more fun to make this fastest-code \$\endgroup\$ – Sp3000 Oct 22 '14 at 7:43
  • 23
    \$\begingroup\$ Downvoting because there's no challenge here. The obvious answer -- just naively implementing the function exactly according to its definition -- is always going to be the best answer. So the question is just "Which language has the least number of characters in the obvious expression of Ackermann's function?" The true winner is the programming language, not the person who wrote the obvious program in it. \$\endgroup\$ – David Richerby Oct 22 '14 at 7:52
  • 1
    \$\begingroup\$ What if my language's recursion limit is too low to compute A(3,8) and above as naively as the others did? Do I have to come up with a non-recursion solution, or can I also just "assume infinite stack space" in these cases? I'm fairly certain, it would terminate within a minute. \$\endgroup\$ – Martin Ender Oct 22 '14 at 9:53
  • 7
    \$\begingroup\$ @DavidRicherby "The obvious answer [...] is always going to be the best answer." This is not true of all languages. I feel a little dirty for only having an example in my home language, but there are multiple ways to express Ackermann and in some languages you can get savings by using that fact. This was my intention for the challenge. \$\endgroup\$ – algorithmshark Oct 22 '14 at 13:15

37 Answers 37

1
2
0
\$\begingroup\$

Ceylon, 88 87 85

alias I=>Integer;I a(I m,I n)=>m<1then n+1else(n<1then a(m-1,1)else a(m-1,a(m,n-1)));

This is a straightforward implementation. Formatted:

alias I => Integer;
I a(I m, I n) =>
        m < 1
        then n + 1
        else (n < 1
            then a(m - 1, 1)
            else a(m - 1, a(m, n - 1)));

The alias saves just one byte, without it (with writing Integer instead of I) we would get to 86 bytes. Another two bytes can be saved by replacing == 0 by < 1 twice.

With the default settings of ceylon run, it will work up to A(3,12) = 32765 (and A(4,0) = 13), but A(3,13) (and therefore also A(4,1)) will throw a stack overflow error. (A(3,12) takes about 5 seconds, A(3,11) about 3 on my computer.)

Using ceylon run-js (i.e. running the result of compiling to JavaScript on node.js) is a lot slower (needs 1 min 19 s for A(3,10)), and breaks already for A(3, 11) with a »Maximum call stack size exceeded« (using default settings) after running for 1 min 30 s.


Ceylon without recursion, 228

As a bonus, here is a non-recursive version (longer, of course, but immune to stack overflows – might get an out-of-memory error at some point).

import ceylon.collection{A=ArrayList}Integer a(Integer[2]r){value s=A{*r};value p=s.addAll;while(true){if(exists m=s.pop()){if(exists n=s.pop()){if(n<1){p([m+1]);}else if(m<1){p([n-1,1]);}else{p([n-1,n,m-1]);}}else{return m;}}}}

Formatted:

import ceylon.collection {
    A=ArrayList
}

Integer a(Integer[2] r) {
    value s = A { *r };
    value p = s.addAll;
    while (true) {
        if (exists m = s.pop()) {
            if (exists n = s.pop()) {
                if (n < 1) {
                    p([m + 1]);
                } else if (m < 1) {
                    p([n - 1, 1]);
                } else {
                    p([n - 1, n, m - 1]);
                }
            } else {
                // stack is empty
                return m;
            }
        }
    }
}

It is quite slower on my computer than the recursive version: A(3,11) takes 9.5 seconds, A(3,12) takes 34 seconds, A(3,13) takes 2:08 minutes, A(3,14) takes 8:25 minutes. (I originally had a version using lazy iterables instead of the tuples I now have, which was even much slower, with the same size).

A bit faster (21 seconds for A(3,12)) (but also one byte longer) is a version using s.push instead of s.addAll, but that needed to be called several times to add multiple numbers, as it takes just a single Integer each. Using a LinkedList instead of an ArrayList is a lot slower.

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 36 bytes

A(m,n){m=m?A(m-1,n?A(m,n-1):1):n+1;}

Naive strategy with a little bit of optimization.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Haskell, 47 bytes

a 0 n=n+1
a m 0=a(m-1)1
a m n=a(m-1)(a m (n-1))

(Run using ghci <filename>) Almost directly copies from the problem definition (thank you pattern matching!).

\$\endgroup\$
2
  • \$\begingroup\$ You may want to include a TIO link so everyone can test your submission? \$\endgroup\$ – RGS Mar 22 '20 at 18:38
  • \$\begingroup\$ I think a(m-1)(a m (n-1)) can be a(m-1).a m$n-1. \$\endgroup\$ – Jonathan Frech Mar 23 '20 at 1:44
0
\$\begingroup\$

APL (Dyalog Unicode), 22 bytes

{0=⍺:1+⍵⋄1∇⍣(⍵+1)⍨⍺-1}

Try it online!

A port of proud haskeller's Haskell answer. Uses the fact that Ack(m,n) is equal to Ack(m-1,?) applied n+1 times to 1.

How it works

{0=⍺:1+⍵⋄1∇⍣(⍵+1)⍨⍺-1}
{                    }  ⍝ ⍺←m, ⍵←n
 0=⍺:1+⍵⋄               ⍝ If m = 0, return 1 + n
          ∇      ⍨⍺-1   ⍝ Apply (m-1)∇ (∇ is recursive call)
           ⍣(⍵+1)       ⍝ n+1 times
         1              ⍝ to the initial value 1
\$\endgroup\$
0
\$\begingroup\$

Erlang (escript), 53 bytes

I tried to put the pattern matching in an if statement; turns out that makes the program longer...

a(0,N)->N+1;a(M,0)->a(M-1,1);a(M,N)->a(M-1,a(M,N-1)).

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Io, 53 bytes

Yet another recursion solution.

a :=method(m,n,if(m<1,n+1,a(m-1,if(n<1,1,a(m,n-1)))))

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Ral, 81 61 bytes

,,/:11+-111:++:+:++:+:+?/0=:1/-/1/10*-0*1:+?+0=11:+?1++/1:+?.

Try it online!

Commented

Code                     Stack after        Description
,,                       0, m, n              Input m and n
                                            Loop:
/:11+-111:++:+:++:+:+?   r, n, m              Jump to SmallM if m < 2
/0=:1/-/1/10*-           r, m-1, 1, m, n-1    Perform [m, n] => [m-1, 1, m, n-1]
0*1:+?                   r, m-1, 1, m, n-1    Jump to Loop if n>0
+0=                      r, m-1, 1            Remove the last two elements
11:+?                    r, m-1, 1            Jump to Loop
                                            SmallM:
1++                      n+m+1, r             Perform [m, n] => [n+m+1]
/1:+?                    n+m+1                Jump to Loop if r>0
.                                             Print n+m+1

Explanation

Because there are no built in function calls (or recursion) in Ral, we need to simulate the stack frame. One way to do that is as follows:

  1. Start with the stack [m, n]
  2. Repeatedly apply the following rules, until a single element remains:
    • [..., 0, n] => [..., n+1]
    • [..., m, 0] => [..., m-1, 1]
    • [..., m, n] => [..., m-1, m, n-1]
  3. Print the remaining element

However, since there is no way to know the current length of the stack in Ral, an additional flag is stored to test if the recursion should continue, resulting in the following rules:

  • [..., 0, 0, n] => Print n+1 and exit
  • [..., 1, 0, n] => [..., n+1]
  • [..., m, 0] => [..., m-1, 1]
  • [..., m, n] => [..., m-1, 1, m, n-1]
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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