Ackermann Function

ack.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <stdarg.h>
#include <vector>

bool g_verbose = false;

// 再帰呼び出し使わない版
int Ack(int m_input, int n_input)
{
    // バッファ確保
    std::vector<int> vtable(1000000); // 100万個 = 4MB
    int ntable = (int)vtable.size();
    int* table = &vtable[0];
    int* table_end = &table[ntable]; // バッファ終端

    // 初期値入れる
    table[0] = m_input;
    table[1] = n_input;

    // 終端位置
    int* end = &table[2];

    // ひたすら計算
    while(1){
        // 要素数が1以下になっていたら計算終了
        int size = end - table;
        if(size <= 1)break;

        // 途中経過表示
        if(g_verbose){
            for(int i = 0; i < size - 2; i++){
                printf("Ack(%d, ", table[i]);
            }
            printf("Ack(%d, %d)", *(end - 2), *(end - 1));
            for(int i = 0; i < size - 2; i++){
                printf(")");
            }
            printf("\n");
        }
    
        // 一番後ろの2つに注目
        int m = *(end - 2);
        int n = *(end - 1);
        if(m == 0){
            // 要素が1個減る
            *(end - 2) = n + 1; // まとめる
            // 終端を変更
            end--;
        }
        else if(n == 0){
            // 要素数は変わらない
            *(end - 2) = m - 1;
            *(end - 1) = 1;
        }
        else{
            // 要素が1個増える
            *(end - 2) = m - 1;
            *(end - 1) = m;
            *(end - 0) = n - 1; // 増えた分
            // 終端を変更
            end++;
            if(end >= table_end){
                printf("ERROR: Table overflow\n");
                exit(1);
            }
        }
    }

    // 計算結果
    if(g_verbose){
        printf("%d\n", table[0]);
    }
    return table[0];
}

int main()
{
    int ack = 0;
    
    printf("---- Calc Ack(2, 1) ----\n");
    g_verbose = true;
    ack = Ack(2, 1);
    printf("--\n");
    printf("Ack(2, 1) = %d\n", ack);
    printf("\n");
    
    printf("---- Calc Ack(4, 1) ----\n");
    g_verbose = false;
    ack = Ack(4, 1);
    printf("--\n");
    printf("Ack(4, 1) = %d\n", ack);
    printf("\n");
    
    return 0;
}