Is there an efficient implementation of tetration?

Question

After recently answering a question involving the Ackerman function part of which involved a function for computing the tetration of a number. Which led me to ponder if there was a more efficient way to do it. I did some testing on my own but I'm limited mainly by the fact that even a number such as 5^^3=5^3125 given 5^3 is roughly 10^2, meaning 5^3125 ~= 10^(3125*2/3) around 2000 digits.

The function doesn't lend itself to divide and conquer methods due to the nature of how the exponentiation is done, ie:

2^^5=2^(2^(2^(2^2))))=2^(2^(2^4))=2^(2^16)=2^65536~=10^(65536*3/10) so around 20k digits...

The nature of the problem, since it begins at the top of the power tree and works it way down strikes me as factorial. A fast power algorithm can be used to do the exponentiation operation obviously, but I haven't been able to see a way to shrink the number of exponentiation operations.

In case anyone is unclear what I'm talking about here's the wiki article , essentially though tetration is:

a^^b= a^a^a....^a, b times and then starting the exponentiation at the top element of the power tree and working down.

The algorithm I'm currently using would be (although I'm using a ruby version if I actually want values):

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

Any thoughts would be appreciated.

Answer 1

With tetration, if the final answer is d digits, then all intermediate results are O(log d) digits, as opposed to O(d) digits with exponentiation. Because the intermediate results for tetration are so small compared to the final result, there's no savings to be had via divide and conquer. It's also unlikely that there is a useful way to save exponentiation operations in a unit-cost RAM, since exponentiation isn't associative.