有没有一个有效的tetration实施？

在最近回答涉及阿克曼函数的问题后，其中一部分涉及用于计算数字系数的函数。这让我深思，是否有更有效的方法来做到这一点。我自己做了一些测试，但主要受限于5^3 = 5^3125这样的数字大概是10^2，这意味着5^3125 = 10 ^（3125 * 2/3）约2000位数字。有没有一个有效的tetration实施？

该函数不借给本身分而治之由于幂是如何完成的性质的方法，即：

2 ^^ 5 = 2 ^（2 ^（2 ^（2^2 ））））= 2 ^（2 ^（2^4））= 2 ^（2^16）= 2^65536 = = 10 ^（65536 * 3/10）因此大约20k位...

问题的本质，因为它从电源树的顶端开始，并且降低了我的工作量，因此我觉得它是阶乘因素。一个快速的功率算法可以用来明显地进行幂运算，但是我一直无法找到缩小指数运算次数的方法。

在任何情况下，目前还不清楚我谈论这里的wiki article，本质上不过是迭代幂次：

一个^^ B = A^A^A^...... A，B三次，然后开始在电源树的顶端元素上取幂，然后继续工作。

目前我使用的是（虽然我使用的红宝石版本，如果我实际上希望值）的算法：

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

任何想法，将不胜感激。

来源

2009-06-08 JSchlather

我认为很多取决于你需要什么样的数字表示。你需要精确的整数表示吗？或者是近似数值（浮点）表示是否足够？ – RBarryYoung 2009-06-08 06:52:26

出于好奇，这纯粹是一个问题，所以我会好奇你怎么才能用浮点表示法编写更高效的算法。 – JSchlather 2009-06-08 14:48:40

我确实研究过这个，但很快就意识到整数数字长度问题（Dave下面解释）也会折磨任何tetration函数输出的指数，只是在一个递归更少的情况下。基本上，浮点可以处理指数乘积，因为它是LOG格式的表示。国际海事组织，为了有效地处理tetration产品，你需要开发一个基于超级日志的格式。这听起来很难但很有趣，甚至可能是有价值的论文（无论如何）。 – RBarryYoung 2009-06-13 00:40:36

如果最终答案是d位，那么所有中间结果都是O（log d）数字，而不是O（d）幂数的指数。因为与最终结果相比，限制的中间结果非常小，所以通过分而治之并不能节省开支。由于指数不关联，因此在单位成本RAM中保存指数运算的方法也不太可能。

来源

2009-06-09 01:42:30 Dave

快速测试证实可以使用相同类型的加速的作为功率算法：

一个↑↑2B =（A^A）

并且甚至更一般：一个↑ⁿ2B =（A↑ⁿ⁻¹一）↑ⁿb

用来确认此代码：

for(long a = 2; a < 5; a++) { 
     for(long b = 2; b < 5; b++) { 
      if(b%2 == 0) { 
       System.out.println(a+"↑↑"+b+"="+tetration(BigInteger.valueOf(a), BigInteger.valueOf(b))); 
       long pow = (long) Math.pow(a, a); // pow = tetration(a,2) 
       System.out.println(pow+"↑↑"+b/2+"="+tetration(BigInteger.valueOf(pow), BigInteger.valueOf(b/2))); 
      } 
     } 
    }

来源

2016-11-12 22:56:54 fejfo

-1

我不认为有一个简单的方法来做到迭代幂次，所以我这样做：

<!DOCTYPE html> 
    <html> 
     <head> 
      <script> 
       var x = 1 
       //That is ▽ The Number You Are Powering// 
       var test = 3 
       var test2 = test 
       setInterval (function() { 
        // that is ▽ How many times you power it so this would be 3 tetra 3  which is 7625597484987// 
        if (x < 3) { 
         document.getElementById('test').innerHTML = test=test2**test 
         x++ 
        } 
       }, 1); 
      </script> 
      <p id="test">0</p>

来源

2016-12-08 15:37:59 derpman1

有没有一个有效的tetration实施？

回答

相关问题