ackermann/ackermann.c at master · cedricbonhomme/ackermann · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h> /* atoi() */

static unsigned int calls;


// Directly from definition
unsigned int naive_ackermann(unsigned int m, unsigned int n) {
    calls++;
    if (m == 0)
        return n + 1;
    else if (n == 0)
        return naive_ackermann(m - 1, 1);
    else
        return naive_ackermann(m - 1, naive_ackermann(m, n - 1));
}

// Partially iterative
unsigned int iterative_ackermann(unsigned int m, unsigned int n) {
    calls++;
    while (m != 0) {
        if (n == 0) {
            n = 1;
        } else {
            n = iterative_ackermann(m, n - 1);
        }
        m--;
    }
    return n + 1;
}

// Precomputed for small m
unsigned int formula_ackermann(unsigned int m, unsigned int n) {
    calls++;
    while(1) {
        switch(m) {
        case 0:  return n + 1;
        case 1:  return n + 2;
        case 2:  return (n << 1) + 3;
        case 3:  return (1 << (n+3)) - 3;
        default:
            if (n == 0) {
                n = 1;
            } else {
                n = formula_ackermann(m, n - 1);
            }
            m--;
            break;
        }
    }
}


int main(int argc, char* argv[]) {
    unsigned int m, n, result;
    m = (unsigned)atoi(argv[1]);
    n = (unsigned)atoi(argv[2]);

    calls = 0;
    result = naive_ackermann(m, n);
    printf("Naive:     %u (%u calls)\n", result, calls);

//     calls = 0;
//     result = iterative_ackermann(m, n);
//     printf("Iterative: %u (%u calls)\n", result, calls);
//
//     calls = 0;
//     result = formula_ackermann(m, n);
//     printf("Formula:   %u (%u calls)\n", result, calls);

    return 0;
}