是否有效实施tetration？

Question

在最近回答涉及Ackerman函数的问题之后,其中一部分涉及计算数字的分解的函数.这让我思考是否有更有效的方法来做到这一点.我自己做了一些测试,但我主要受限于这样一个事实,即5 ^^ 3 = 5 ^ 3125给出5 ^ 3的数字大约是10 ^ 2,意味着5 ^ 3125~ = 10 ^(3125*2/3)大约2000位数.

由于取幂的性质,该函数不适用于划分和征服方法,即:

2 ^^ 5 = 2 ^(2 ^(2 ^(2 ^ 2))))= 2 ^(2 ^(2 ^ 4))= 2 ^(2 ^ 16)= 2 ^ 65536〜= 10 ^( 65536*3/10)所以大约20k位......

这个问题的本质,因为它从功率树的顶部开始并且向下工作,这使我感觉像是阶乘的.可以使用快速功率算法来进行取幂运算,但是我还没有看到缩小取幂运算次数的方法.

如果有人不清楚我在说什么是wiki文章,基本上虽然tetration是:

a ^^ b = a ^ a ^ a ... ^ a,b次,然后在幂树的顶部元素处开始取幂并向下运算.

我目前正在使用的算法是(虽然如果我真的想要值,我使用的是ruby版本):

long 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;
}

任何想法将不胜感激.

Answer 1

使用四定法，如果最终答案是 d 位数字，则所有中间结果都是 O(log d) 位数字，而不是乘幂的 O(d) 位数字。由于与最终结果相比，tetration 的中间结果非常小，因此通过分而治之无法节省成本。也不可能存在一种有用的方法来将求幂运算保存在单位成本 RAM 中，因为求幂不具有关联性。