Tetration Operator in Math Simply Explained with Python Algorithms

ACMer

1 year ago

What is Tetration Operator in Math?

Tetration is an operation in mathematics that involves iterated exponentiation. It is part of the sequence of hyperoperations that extend beyond addition, multiplication, and exponentiation. In tetration, a number is raised to the power of itself repeatedly a specified number of times.

The notation for tetration of a number a with height n is usually written as: or (a↑↑n) This means a is exponentiated n times. For example:

(simple identity)
(a raised to the power of itself once)
(a raised to the power of itself )
, and so on and so forth.

In the context of tetration, is not commonly defined or universally agreed upon. However, some mathematical conventions suggest that for any , similar to how for any non zero in exponentiation.

Example of Tetration

Let’s evaluate (read as “tetrate 2 to height 3”):

General Properties of Tetration Operator

Non-Commutative: Tetration is not commutative, meaning
Very Fast Growth: Tetration grows extremely quickly. Even small numbers can lead to extremely large results due to the rapid growth of exponentiation.

Tetration is an operation less frequently encountered in basic mathematics, but it plays a role in certain areas of advanced mathematics, particularly in areas like large number theory and computer science where extremely large numbers are involved.

Compute Tetration Operator in Python

Here are two Python functions to compute tetration. The first function uses recursion, and the second one uses iteration.

In both functions, we added a check for n = 0 at the beginning. If n is 0, the function returns 1, Otherwise, it proceeds as before. This way, the functions handle n=0 according to the convention that any number tetrated to the height of 0 is 1.

Recursive Function to Compute the Tetration

Recursive Function: This function calls itself with the height n decreased by 1 until it reaches 1, at which point it returns the base a. This gives the effect of building the exponentiation chain from the top down.

@lru.cache(None)  ## caching the function
def tetration_recursive(a, n):
    if n == 0:
        return 1
    if n == 1:
        return a
    return a ** tetration_recursive(a, n - 1)

he recursive function for computing tetration could theoretically be tail-optimized. In tail recursion, the recursive call is the last operation in the function, allowing certain compilers or interpreters to optimize the call stack usage by reusing the same stack frame. This can help reduce the space complexity to O(1) by eliminating the need for additional stack frames for each recursive call.

However, the current recursive implementation is not tail-recursive, because the recursive call is nested within an exponentiation operation:

return a ** tetration_recursive(a, n - 1)

Here, the exponentiation operation depends on the result of the recursive call, so the result must be computed before completing the current call, preventing tail recursion optimization.

Iterative Function to Compute the Tetration

Iterative Function: This function uses a for loop to iterate through the height n, computing the result in a bottom-up manner by updating the result variable with the exponentiation in each iteration.

def tetration_iterative(a, n):
    if n == 0:
        return 1
    result = a
    for _ in range(1, n):
        result = a ** result
    return result

Time/Space Complexity of Tetration Algorithms

The time and space complexity of the Python functions for computing tetration differ based on whether they are implemented recursively or iteratively. Let’s analyze both implementations.

Recursive Function Complexity

Time Complexity:

Each recursive call makes one exponentiation operation with the result from the previous call.
There are n-1 recursive calls in total, so the function is called O(n) times.
However, exponentiation operations like take time.
Therefore, for larger values of n, the time complexity becomes exponential due to the nature of repeated exponentiation.
This results in an overall time complexity of approximately with n levels, meaning it grows extremely quickly

Space Complexity:

Since this is a recursive function, it uses stack space for each call.
The maximum depth of recursion is n, so the space complexity is O(n).

Iterative Function Complexity

Time Complexity:

Like the recursive version, the function iterates n – 1 times
Each iteration involves computing raised to the power of result, which grows exponentially.
Therefore, the time complexity also becomes with n levels, due to the exponential growth at each step.

Space Complexity:

his iterative version only requires a fixed amount of extra space for variables like result, so it has O(1) additional space complexity.
However, the result itself can grow extremely large, potentially requiring a significant amount of memory to store if a and n are large.

Both implementations face extremely high time complexity due to the rapid growth of the result with repeated exponentiation, which becomes impractical for large values. The recursive version has a space complexity of O(n) due to call stack usage, while the iterative version has O(1) auxiliary space complexity but still handles extremely large numbers, which can impact memory usage indirectly.

Math

–EOF (The Ultimate Computing & Technology Blog) —

1722 words
Last Post: Teaching Kids Programming - Convert Array to Linked List and Vice Versa
Next Post: Site Reliability Engineer (SRE) vs Software Engineer

The Permanent URL is: Tetration Operator in Math Simply Explained with Python Algorithms (AMP Version)