Ackermann function iterative-recursive form in C

Question

I am trying to write the Ackermann function iterative in m and recursive in n. I got to this point where the code I provided below work for all values below Ack(5,0) but it overflows after this value. I am not sure where and I am not sure how to optimize it. What I am trying to achieve is this:

$$Ack(m,n)=Ack(m-1,Ack(m,n-1))=Ack(m-2,Ack(m-1,Ack(m,n-1))-1)=Ack(m-3,Ack(m-2,Ack(m-1,Ack(m,n-1))-1)-1)$$ and so on.

Here is the code:

unsigned long long Ackermann_itm_recn(int m, unsigned long long n){
 unsigned long long Ack=0;
 if (m==0){
 Ack = n+1;
 }
 else if(n==0){
 Ack = Ackermann_itm_recn(m-1,1);
 }
 else{
 Ack=Ackermann_itm_recn(m-1,Ackermann_itm_recn(m,n-1));
 for(int i=2;i<=m-2;i++){
 Ack= Ackermann_itm_recn(m-i,Ack-1);
 }
 }
 return Ack;
}
int main(){
 printf("%lld \n", Ackermann_itm_recn(4,0));
}

• ChrisWue: This would probably a better question for SO and not Code Review. Code Review is all about reviewing existing working code and not to solve specific problems.
• ChrisWue: Yes, I think that would be best unless you want to rephrase your question to just ask for a code review and general improvement tips.
• anton: I changed the question
• ChrisWue: Well, the Ackerman function grows extremely quickly, A(5, 0) is the only value you can compute in 64 bit for m=5, for m=4 you can compute n=0,1, for m=3 you can compute n=0..61 - check en.wikipedia.org/wiki/Ackermann_function
• greybeard: I find no programming error with the code presented. The way to compute the Ackermann-Péter function is stated clearly. Asking how to optimize, do the same for the goal of improvement.

Answer 1

Declaring main() instead of main(void) is Incorrect (Until C23)

This is a deprecated way of declaring a K&R-style variadic function. C23 will redefine this to mean the same thing as main(void), as C++ has done for decades.

C17 says that the two allowed definitions are int main(void) or int main(int argc, char* argv[]) (or compatible). This isn’t just language-lawyering either: on some implementations, K&R-style functions have a different calling convention.

Scalars that Cannot be Less than 0 Should be unsigned Types

You declare int m, but this form of the Ackermann function is only defined for non-negative integers.

Also, if the parameters should not be modified, declare them const in the function definition. (There are no function prototypes in this program, but it is not necessary there.)

Use a 128-bit Type if You Have One

Your values are overflowing unsigned long long int, but there is no portable 128-bit type in C17.

Adding uintmax_t to the Standard turned out to be a mistake, because implementations weren’t able to change it and break their ABI, but also weren’t allowed to have any type wider than it. This prevented many implementations from having an unsigned 128-bit type.

C23, however, is going to redefine uintmax_t so that there can be integers wider than it. C23 will also allow

typedef unsigned _BitInt(128) u128

for a portable, 128-bit unsigned type.

Use Standard Naming Conventions

Function names are not normally capitalized in C, even when they happen to be named after a person or proper noun.

You Can Optimize With a Tail-Recursive Implementation

This isn’t the conventional way to write C, but several compilers, including Clang, ICX and ICPX, support an extension that tells the compiler to always perform tail-call optimization. I often use it with this boilerplate:

#if defined(__clang__) || defined(__INTEL_LLVM_COMPILER )
# define MUSTTAIL __attribute((musttail))
#else
# define MUSTTAIL /**/
#endif

This makes MUSTTAIL return ackermann_tr(m-1, 1); expand to the proper compiler extension to force tail-call elimination on compilers that support it, or to a plain return statement on compilers that don't.

With Clang 17.0.1 using -std=c17 -march=x86-64-v3 -O3, this tail-recursive version:

#if defined(__clang__) || defined(__INTEL_LLVM_COMPILER )
# define MUSTTAIL __attribute((musttail))
#else
# define MUSTTAIL /**/
#endif
unsigned long long ackermann_tr( const unsigned m, 
 const unsigned long long n
 ) {
 if (m == 0) {
 return n+1;
 } else if (n == 0) {
 MUSTTAIL return ackermann_tr(m-1, 1);
 } else {
 MUSTTAIL return ackermann_tr(m-1, ackermann_tr(m, n-1));
 }
}

generates the following code:

ackermann_tr: # @ackermann_tr
 mov rax, rsi
 test edi, edi
 je .LBB1_6
 push rbx
 mov ebx, edi
 jmp .LBB1_2
.LBB1_3: # in Loop: Header=BB1_2 Depth=1
 mov eax, 1
 dec ebx
 je .LBB1_5
.LBB1_2: # =>This Inner Loop Header: Depth=1
 test rax, rax
 je .LBB1_3
 dec rax
 mov edi, ebx
 mov rsi, rax
 call ackermann_tr
 dec ebx
 jne .LBB1_2
.LBB1_5:
 pop rbx
.LBB1_6:
 inc rax
 ret

Particularly note that only the nested call to ackermann_tr within the else case needs a call instruction, and all others are optimized by jumps. For the original implementation, the compiler with the same settings generates the code:

Ackermann_itm_recn: # @Ackermann_itm_recn
 push rbp
 push rbx
 push rax
 mov rax, rsi
 test edi, edi
 je .LBB0_3
 mov ebx, edi
 test rax, rax
 jne .LBB0_4
 mov eax, 1
 dec ebx
 je .LBB0_3
.LBB0_4:
 lea ebp, [rbx - 1]
 dec rax
 mov edi, ebx
 mov rsi, rax
 call Ackermann_itm_recn
 mov edi, ebp
 mov rsi, rax
 call Ackermann_itm_recn
 cmp ebx, 4
 jl .LBB0_7
 add ebx, -3
.LBB0_6: # =>This Inner Loop Header: Depth=1
 lea edi, [rbx + 1]
 dec rax
 mov rsi, rax
 call Ackermann_itm_recn
 dec ebx
 jne .LBB0_6
.LBB0_7:
 add rsp, 8
 pop rbx
 pop rbp
 ret
.LBB0_3:
 inc rax
 add rsp, 8
 pop rbx
 pop rbp
 ret

Note that this has significantly more instructions and requires more call instructions, each of which has to create a new stack frame.

GCC and MSVC do not support the musttail compiler extension, but GCC performs the optimization without needing a hint. MSVC does not.

You can try out the code on Godbolt.

• ChrisWue: Just as a comment: For Ackermann, 128 bit won't really get you much further than 64 bit. Going from A(4, 1) to A(4, 2) for example goes from requiring 16 bits to requiring 65536 bits
• chux: int main() is fine. C17 says that the two allowed definitions as well as "or in some other implementation-defined manner.". C99/C11 specs use int main() in example code. A function definition using f() has been the same as f(void) since, IIRC, C99. What has changed in C17 relates to f() as a declaration, something OP is not doing here.
• chux: "Function names are not normally capitalized in C" is a truism for standard library functions. Yet much user code uses uppercase in names. That is a style issue.
• chux: "because implementations weren’t able to change it and break their ABI" sounds like a self imposed problem not of the language, but of the user code. One can certainly write code using (u)intmax_t and deal with growth. Same thing happened with long as 32 then 64 bit. What is tricky about (u)intmax_t is that is the type used by the pre-processor and assuming that is 64-bit leads to issues.
• chux: "parameters should not be modified, declare them const." is a style issue. In select cases, it is useful in function definitions, yet at the cost of some clutter. In function declarations, it adds no value, just clutter. Note the standard C library does not use const on any function parameter in the declarations. (Of course const is used on the pointed to types)

Answer 2

Only small stuff, no optimization suggestions.

Save time, enable all warnings

Mismatched specifier.
Consider dropping spaces before a '\n'.

// printf("%lld \n", Ackermann_itm_recn(4,0));
printf("%llu\n", Ackermann_itm_recn(4,0));

Negative m?

Code goes off the rails when m < 0. Perhaps an assert(m >= 0) or use unsigned:

// unsigned long long Ackermann_itm_recn(int m, unsigned long long n){
unsigned long long Ackermann_itm_recn(unsigned m, unsigned long long n){
// Avoid trouble when m == 1
// for(int i=2;i<=m-2;i++){
for(unsigned i = 2; i + 2 <= m; i++) {

uintmax_t?

Common today that uintmax_t and unsigned long long are the same range, yet why not use a potential wider type?

#include <inttypes.h>
uintmax_t Ackermann_itm_recn(int m, uintmax_t n) {
 ...
printf("%ju\n", Ackermann_itm_recn(4,0));