1
\$\begingroup\$

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));
}
\$\endgroup\$
7
  • \$\begingroup\$ 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. \$\endgroup\$
    – ChrisWue
    Oct 16, 2023 at 23:10
  • \$\begingroup\$ ok thanks, should i delete the problem? \$\endgroup\$
    – anton
    Oct 16, 2023 at 23:11
  • \$\begingroup\$ 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. \$\endgroup\$
    – ChrisWue
    Oct 16, 2023 at 23:14
  • 1
    \$\begingroup\$ I changed the question \$\endgroup\$
    – anton
    Oct 17, 2023 at 0:27
  • \$\begingroup\$ 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 \$\endgroup\$
    – ChrisWue
    Oct 17, 2023 at 2:23

2 Answers 2

3
\$\begingroup\$

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));
\$\endgroup\$
0
3
\$\begingroup\$

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.

\$\endgroup\$
13
  • \$\begingroup\$ 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 \$\endgroup\$
    – ChrisWue
    Oct 18, 2023 at 5:34
  • \$\begingroup\$ 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. \$\endgroup\$ Oct 18, 2023 at 6:17
  • \$\begingroup\$ "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. \$\endgroup\$ Oct 18, 2023 at 6:27
  • \$\begingroup\$ "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. \$\endgroup\$ Oct 18, 2023 at 6:32
  • \$\begingroup\$ "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) \$\endgroup\$ Oct 18, 2023 at 6:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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