计算较大的ackermann函数值

Question

我有一些代码:

int CalculateAckermann(int x, int y)
{
    if(!x)
    {
        return y++;
    }
    if(!y)
    {
        return CalculateAckermann(x--,1);
    }
    else
    {
        return CalculateAckermann(x--, CalculateAckermann(x, y--));
    }
}

旨在计算ackermann函数.在相当低的x和y数量之上,应用程序会导致堆栈溢出,因为它会过度递归并导致相当大的数字.我如何慢慢计算解决方案？

Answer 1

作为注释,如果您希望仅使用闭合形式,则m <4的算法很简单.如果你想扩展到tetration,那么我建议你写一个fastpower算法,可能使用二进制方法,然后用这个方法你可以写一个tetration函数.看起来像这样:

int Tetration(int number, int tetrate)
{
    long int product=1;
    if(tetrate==0)
        return product;
    product=number;
    while(tetrate>1)
    {
        product=FastPower(number,product);
        tetrate--;
    }
    return product;
}

然后你可以覆盖n == 4之前的情况,之后使用递归定义和A(5,n)溢出的值以荒谬的速度,所以它真的没关系.虽然你的老师可能不会对这样的算法感到满意,但它的运行速度会快得多.在我的一个离散类中,当我要求编写一个算法来计算斐波纳契数,然后找到它的O(n)时,我写了封闭的形式,然后写了O(1)并得到了充分的信任,一些教授欣赏聪明的答案.

关于Ackerman函数的重要注意事项是它基本上定义了整数上的加法函数的heirachy,A(1,n)是加法,A(2,n)是乘法,A(3,n)是取幂,A (4,n)是tetration,5之后函数增长得太快而不适用.

查看加法,乘法等的另一种方法是:

?0 (x, y ) = y + 1
?1 (x, y ) = +(x, y )
?2 (x, y ) = ×(x, y )
?3 (x, y ) = ? (x, y )
?4 (x, y ) = ?? (x, y )
           = ?4 (x, 0) = 1 if y = 0
           = ?4 (x, y + 1) = ?3 (x, ?4 (x, y )) for y > 0

(使用前缀表示法,即+(x,y)= x + y,(x,y)= x y.

Answer 2

IIRC,Ackermann函数的一个有趣特性是评估它所需的最大堆栈深度(在调用级别)与函数的答案相同.这意味着可以通过硬件虚拟内存的限制对实际计算进行严格限制.具有多精度算术包是不够的; 你需要更多的比特来存储数字对数的对数,而不是宇宙中的亚原子粒子.

再次,IIRC,你可以得到相对简单的A(1,N),A(2,N)和A(3,N)的闭合公式,沿着以下几行(我似乎记得在答案中有3个) ,但细节可能不正确):

• A(1,N)= 3 + N.
• A(2,N)= 3*N.
• A(3,N)= 3 ^ N.

A(4,N)的公式涉及一些挥动和堆叠指数N-deep.然后A(5,N)的公式包括堆叠A(4,N)的公式......它变得非常奇怪且非常快速昂贵.

随着公式变得更加复杂,计算变得完全无法管理.

关于Ackermann功能的维基百科文章包括"价值表"部分.我的记忆生疏了(但是20年前我最后一次看过这个),它给出了封闭的公式:

• A(0,N)= N + 1
• A(1,N)= 2 +(N + 3)-3
• A(2,N)= 2*(N + 3)-3
• A(3,N)= 2 ^(N + 3)-3

并且A(4,N)= 2 ^ 2 ^ 2 ^ ... - 3(其中2是2的幂,N + 3次).

Answer 3

(感觉像是一个家庭作业问题,但无论如何我都会回答......)

阅读有关Ackermann功能的更多信息.例如,WikiPedia的文章说

"即使是小输入,它的价值也会迅速增长.例如A(4,2)是一个19,729十进制数的整数".

我怀疑你的32位(或64位,取决于你的架构)整数是溢出的,你因为这些问题而进入无限循环.简单的printf样式调试将显示整数溢出.如果你想实际计算Ackermann函数,你需要使用无限精度bignum库,比如GNU MP.

另外,阅读Tail Recursion,以及如何优化它.