时间戳

首页 > 解决方案 > C 中的 Ackermann 函数 (4, 1) 不计算 - Ackermann with Caching

c - C 中的 Ackermann 函数 (4, 1) 不计算 - Ackermann with Caching

问题描述

在使用高级语言完成工作（MATLAB、R）一段时间后，我最近对 ​​C 非常感兴趣，并且正在使用它来尝试更好地理解软件和硬件之间的交互。我写了一个非常简单的递归函数来计算阿克曼：

int ackermann(int m, int n)
{
    if (m == 0)
    {
        return n + 1;
    }

    if (m > 0 && n == 0)
    {
        return ackermann((m - 1), 1);
    }

    if (m > 0 && n > 0)
    {
        return ackermann((m - 1), ackermann(m, (n - 1)));
    }
}

（当然，带有 form和nin的循环main）适用于高达 (4, 1) 的值。我知道这是一个相当大的值，超出此计算是不可行的。我在驱动程序循环中添加了一些打印语句来弄清楚发生了什么：

 for (int m = 0; m < 5; m++)
    {
        for (int n = 0; n < (6 - m); n++)
        {
            printf("\nCalculating Ackermann of (%d, %d)...\n", m, n);
            printf("Ackermann(%d, %d) = %d \n", m, n, ackermann(m, n));
        }
    }

它Calculating Ackermann of (4, 1)...停留大约 5 秒左右，然后程序停止。尽管我不能确定它没有耗尽资源，但它似乎并没有吞噬内存。

我去寻找一个解决方案，并在一个名为 RosettaCode.com 的网站上偶然发现了这段代码。作者表示它缓存了一些已知值以允许计算一些更大的值。

相当大胆，但有人可以解释这是在做什么吗？我以前见过左位移<<，我知道这malloc是用于动态内存分配（所以我假设这是处理预缓存变量的数组？）但是这storage_bits让我完全困惑（我感兴趣，但不熟悉这种低级的东西）。

// Ackermann function with caching - Understand how the bit-shift works?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int m_storageBits = 0;
int n_storageBits = 0;
int *valCache;

long int ackFunc(int m, int n)
{
    int cacheIndex = 0;
    int ackResult  = 0;

    if(!m)
    {
        return (n + 1);
    }
    if (n >= 1 << n_storageBits)
    {
        printf("%d, %d\n", m, n);
        cacheIndex = 0;
    } else {
        cacheIndex = (m << n_storageBits) + n;
        if (valCache[cacheIndex])
        {
            return valCache[cacheIndex];
        }
    }

    if (!n)
    {
        ackResult = ackFunc((m - 1), 1);
    } else {
        ackResult = ackFunc((m - 1), ackFunc(m, n - 1));
    }

    if (cacheIndex)
    {
        valCache[cacheIndex] = ackResult;
        return ackResult;
    }

    return 0;
}

int main()
{
    int m = 0;
    int n = 0;

    // Specify value size that may be saved
    m_storageBits = 3;
    m_storageBits = 20;   // 2**20, ~1 megabyte

    valCache = malloc(sizeof(int) * (1 << (m_storageBits + n_storageBits)));
        printf("\nValue cache before memset: %i", valCache);
    memset(valCache, 0, sizeof(int) * (1 << (m_storageBits + n_storageBits)));
        printf("\nValue cache after memset: %i", valCache);

    for (m = 0; m <= 4; m++)
    {
        for (n = 0; n <= 6 - m; n++)
        {
            printf("\nCalculating Ackermann of (%d, %d)...\n", m, n);
            printf("Ackermann(%d, %d) = %d\n", m, n, ackFunc(m, n));
        }
    }

    return 0;
}

如您所见，我在 周围添加了一些打印语句，memset但值看起来相同。我尝试了几种不同的格式，但老实说，我不确定如何正确输出，或者是否可以正确输出。我已经更改了一些语法，并根据我从代码中可以理解的内容，用一些更有用的描述符替换了完全无用的一字符或三字符变量名。

正如我所说，我很大胆地请人梳理一下并向我解释，但我很难过。如果不是，我会很高兴理解为什么我的简化方法在 ack(4, 1) 处失败（这要求很高，但我有一个相当现代的 ThinkPad）。

谢谢！帮助表示赞赏。

标签： c

解决方案

正如我所说，我很大胆地请人梳理一下并向我解释，但我很难过。如果不是，我会很高兴理解为什么我的简化方法在 ack(4, 1) 处失败（这要求很高，但我有一个相当现代的 ThinkPad）。

我将使用 Python 来说明，因为它具有内置的 dict 类型。

import sys
sys.setrecursionlimit(16392)

cache = {}


def ackermann(m, n):
    if m == 0:
        return (n + 1, 1)

    if (m, n) in cache:
        return cache[(m, n)]

    if n == 0:
        r = cache[(m, n)] = ackermann(m - 1, 1)
        return r

    r1, e1 = ackermann(m, n - 1)
    r2, e2 = ackermann(m - 1, r1)
    r = cache[(m, n)] = (r2, e1 + e2)
    return r


print(ackermann(4, 1))

代码有点乱——通过functools.lru_cache在我的平台上运行与 C 堆栈冲突来简化——但重要的是它评估 A(4, 1)并跟踪在ackermann没有缓存的情况下会产生多少次调用.

(65533, 1431459240)

1,431,459,240 是很多电话，即使对于相当现代的 ThinkPad 来说也是如此。

至于 C 代码：它在做同样的事情，保持 (m, n) 到 A(m, n) 的映射以避免调用次数激增，但是因为 C 没有内置的哈希表，它通过使用一大块内存作为二维数组来保持简单，其中每个索引的最低有效n_storageBits位代表 n，其余位代表 m。这就是位移的作用。

  • A(4, 1) 被评估
  • (4, 1) 以这样的方式转换为索引，即每个支持的 (M, N) 对都会产生不同的结果，在这种情况下，选择 2 b M + N 并且选择 b 使得对于任何支持的 N ，N < 2 b
  • 该索引用于查找并将结果存储在一个大小为 2 b M + N + 1 的数组中，以获得最大支持的 M。

推荐阅读